企业网站源码交易,建筑网站建设方案,wordpress 主题 xiu,中国优秀网站水题盛宴啦啦啦……做起来真的极其舒服#xff0c;比某些毒瘤题好太多了…… 数据范围极小 -- 状压 / 搜索 / 高维度dp#xff1b;观察要求的均方差#xff0c;开始考虑是不是能够换一下式子。我们用\(a_{x}\)来表示第 \(x\) 个矩阵的总值#xff0c;则式子为#xff… 水题盛宴啦啦啦……做起来真的极其舒服比某些毒瘤题好太多了…… 数据范围极小 -- 状压 / 搜索 / 高维度dp观察要求的均方差开始考虑是不是能够换一下式子。我们用\(a_{x}\)来表示第 \(x\) 个矩阵的总值则式子为 \(ans sqrt \frac{{\left ( \sum_{1}^{n} a_{x} - \bar{x} \right )^2}}{n}\) 转化一下化成 \(ans sqrt \frac{{\left ( -n\bar{x}^2 \sum_{1}^{n}a_{x}^2 \right )}}{n}\) 然后问题就变成了使划分出来的矩阵的平方和最小。直接上记忆化搜索BINGO~ #include bits/stdc.h
using namespace std;
#define maxn 11
#define INF 99999999
#define db double
int n, m, K, sum[maxn][maxn];
int f[maxn][maxn][maxn][maxn][maxn];
int tot;
db aver;int read()
{int x 0;char c;c getchar();while(c 0 || c 9) c getchar();while(c 0 c 9) x x * 10 c - 0, c getchar();return x;
}int dfs(int a, int b, int c, int d, int K)
{int *F f[a][b][c][d];if(~F[K]) return F[K];else F[K] INF;if(c * d - (a - 1) * (b - 1) K) return F[K] INF;if(K 1){F[K] sum[c][d] - sum[a - 1][d] - sum[c][b - 1] sum[a - 1][b - 1];return F[K] F[K] * F[K];}for(int i a; i c; i )for(int j 1; j K; j ){ int x1 dfs(a, b, i, d, j);int x2 dfs(i 1, b, c, d, K - j);F[K] min(F[K], x1 x2);} for(int i b; i d; i )for(int j 1; j K; j ){int x1 dfs(a, b, c, i, j);int x2 dfs(a, i 1, c, d, K - j);F[K] min(F[K], x1 x2);}return F[K];
}int main()
{n read(), m read(), K read();memset(f, -1, sizeof(f));for(int i 1; i n; i )for(int j 1; j m; j ){int x read(); tot x;sum[i][j] sum[i - 1][j] sum[i][j - 1] - sum[i - 1][j - 1] x;}db aver (db) tot / K;dfs(1, 1, n, m, K);printf(%.2f\n, sqrt(((db) f[1][1][n][m][K] - aver * aver * (db) (K)) / (db) K));return 0;
} 转载于:https://www.cnblogs.com/twilight-sx/p/9027775.html
