[HAOI2007] 分割矩阵
显然，最终的平均值不变。
这样，我们设f[w,a,b,c,d]为在矩形[a~c,b~d]中割了w刀的根号内分子和。
那么，状态转移有f[w,a,b,c,d] = min
f[p,a,b,k,d]+f[w-p-1,k+1,b,c,d]
f[p,a,b,c,k]+f[w-p-1,a,k+1,c,d]
初始化为 f[0,a,b,c,c,d]=sqr (sum[a~c,b~d] - ave)
阶段是割的次数。dp就好了。
答案最终除以t再开根号。
附录：
均方差，通常指标准差 ，表达式为
\[ \sqrt{\frac{\sum_{i=1}^N (x_i-\bar x)}{N}} \]
#include
using namespace std;int n,m,t;
double s[11][11],ave;
double f[30][11][11][11][11]; double sum(int a,int b,int c,int d) {return s[c][d]-s[a-1][d]-s[c][b-1]+s[a-1][b-1];
}
double sqr(double x) {return x*x;
}
void upmin(double&x,const double&y) {if(y 转载于:https://www.cnblogs.com/nosta/p/10177550.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！