网站怎么添加百度商桥,网站后台树形菜单样式,网络营销和网络推广有什么区别,asp音乐网站开发教程题目描述
将一个8*8的棋盘进行如下分割#xff1a;将原棋盘割下一块矩形棋盘并使剩下部分也是矩形#xff0c;再将剩下的部分继续如此分割#xff0c;这样割了n-1次后#xff0c;连同最后剩下的矩形棋盘共有n块矩形棋盘。 (每次切割都只能沿着棋盘格子的边进行)
原棋盘上…题目描述
将一个8*8的棋盘进行如下分割将原棋盘割下一块矩形棋盘并使剩下部分也是矩形再将剩下的部分继续如此分割这样割了n-1次后连同最后剩下的矩形棋盘共有n块矩形棋盘。 (每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘并使各矩形棋盘总分的均方差最小。求出均方差的最小值。 其中均方差的定义为 里面的括号应该还有一个平方不然固输0岂不美哉
数据范围
1n15所有数均为不大于100的非负整数
解析
分析题面可以发现一些结论 1.只要大矩阵与n确定平均值就是可以算出的定值 2.每次分完后只能对其中的一部分继续切割 对于第2条举个例子n4时田字型的切割就是不合法的这对于本题至关重要 我们可以先算出均方差根号里面那个西格玛加和的总值的最小值最后再除n开根号 定义dp[x1][y1][x2][y2][k]:左上角为x1,y1,右下角为x2,y2还可以切k刀时切成的k1部分西格玛方差的最小值 显然k0时
if(k0) return abs((double)he(x1,y1,x2,y2)-ave)*abs((double)he(x1,y1,x2,y2)-ave);ave为提前可算好的平均值he函数可以用二维前缀和O1求出具体见代码其实遍历求本题时间可能也爆不了。。。 对于转移我们枚举切出去的那个不能再切的矩形的位置即可
代码
#include cstdio
#include cstring
#include cmath
#include algorithm
#include iostream
#include string
#include queue
#include string
#includemap
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a));
#define ull unsigned ll
using namespace std;
const int N15;
int m,n,tot;
int mp[10][10],sum[10][10];
double ave;
double dp[N][N][N][N][N];
int he(int x1,int y1,int x2,int y2){return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]sum[x1-1][y1-1];
}
double find(int x1,int y1,int x2,int y2,int k){if(dp[x1][y1][x2][y2][k]) return dp[x1][y1][x2][y2][k];if(k0) return abs((double)he(x1,y1,x2,y2)-ave)*abs((double)he(x1,y1,x2,y2)-ave);dp[x1][y1][x2][y2][k]1e9;for(int ix1;ix2;i){//横着切 dp[x1][y1][x2][y2][k]min(dp[x1][y1][x2][y2][k],find(x1,y1,i,y2,0)find(i1,y1,x2,y2,k-1));dp[x1][y1][x2][y2][k]min(dp[x1][y1][x2][y2][k],find(x1,y1,i,y2,k-1)find(i1,y1,x2,y2,0));//注意这里还要反着枚举一遍因为不能切的部分可能在下边 }for(int jy1;jy2;j){//竖着切 dp[x1][y1][x2][y2][k]min(dp[x1][y1][x2][y2][k],find(x1,y1,x2,j,0)find(x1,j1,x2,y2,k-1));dp[x1][y1][x2][y2][k]min(dp[x1][y1][x2][y2][k],find(x1,y1,x2,j,k-1)find(x1,j1,x2,y2,0));}return dp[x1][y1][x2][y2][k];
}
int main(){scanf(%d,n);for(int i1;i8;i){for(int j1;j8;j) scanf(%d,mp[i][j]);}for(int i1;i8;i){for(int j1;j8;j) sum[i][j]sum[i][j-1]mp[i][j];}for(int j1;j8;j){for(int i1;i8;i) sum[i][j]sum[i-1][j];}ave1.0*sum[8][8]/n;printf(%.3lf,sqrt(1.0*find(1,1,8,8,n-1)/n));
}
/*
样例
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3ans:1.633
*/心得
一次AC万岁
这道dp做的还是不错的尤其是很快发现了解析中提到的两条关键结论从而带出了思路 所以要仔细审题 dp就像数学平几有时候思路一下子通了就不难了awa
thanks for reading!
