首页 > 代码库 > POJ 1191 DP+DFS棋盘分割问题
POJ 1191 DP+DFS棋盘分割问题
题目大意：
Description
将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
，其中平均值
，xi为第i块矩形棋盘的总分。 请编程对给出的棋盘及n，求出O‘的最小值。
，其中平均值，xi为第i块矩形棋盘的总分。 请编程对给出的棋盘及n，求出O‘的最小值。
运用动态规划，状态为int d(int k, int x1, int y1, int x2, int y2)，表示左上角为(x1, y1)，右下角为(x2, y2)的矩阵被切割成n块时可以达到的最小平方和。
状态转移方程为
nowstate=min( nowstate, dfs(k-1, x1, y1, a ,y2)+s[a+1, y1, x2, y2])
nowstate=min( nowstate, dfs(k-1, a+1, y1, x2, y2)+s[x1, y1, a, y2])
nowstate=min( nowstate, dfs(k-1, x1, b+1, x2, y2)+s[x1, y1, x2, b])
nowstate=min( nowstate, dfs(k-1, x1, y1, x2, b)+s[x1, b+1, x2, y2])
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 #define INF 0x3f3f3f3f 7 int dp[15][9][9][9][9],val[9][9],n; 8 9 int sum(int x1,int y1,int x2,int y2)10 {11 int ans=val[x2][y2]-val[x1-1][y2]-val[x2][y1-1]+val[x1-1][y1-1];12 return ans*ans;13 }14 15 int dfs(int k,int x1,int y1,int x2,int y2)16 {17 if(dp[k][x1][y1][x2][y2]) return dp[k][x1][y1][x2][y2];18 if(k==1||x1==x2||y1==y2){19 dp[k][x1][y1][x2][y2]= sum(x1,y1,x2,y2);20 return dp[k][x1][y1][x2][y2];21 }22 int nowstate=INF;23 for(int i=x1;i<x2;i++){24 nowstate=min(nowstate,dfs(k-1,i+1,y1,x2,y2)+sum(x1,y1,i,y2));25 nowstate=min(nowstate,dfs(k-1,x1,y1,i,y2)+sum(i+1,y1,x2,y2));26 }27 for(int i=y1;i<y2;i++){28 nowstate=min(nowstate,dfs(k-1,x1,i+1,x2,y2)+sum(x1,y1,x2,i));29 nowstate=min(nowstate,dfs(k-1,x1,y1,x2,i)+sum(x1,i+1,x2,y2));30 }31 dp[k][x1][y1][x2][y2]=nowstate;32 return nowstate;33 }34 35 void change()36 {37 for(int i=0;i<=8;i++)38 val[i][0]=0,val[0][i]=0;39 40 for(int i=1;i<=8;i++)41 for(int j=1;j<=8;j++)42 val[i][j]+=val[i-1][j]+val[i][j-1]-val[i-1][j-1];43 }44 45 int main()46 {47 while(~scanf("%d",&n)){48 49 memset(dp,0,sizeof(dp));50 51 for(int i=1;i<=8;i++)52 for(int j=1;j<=8;j++)53 scanf("%d",&val[i][j]);54 55 change();56 57 double res;58 double ave=1.0*val[8][8]/n;59 res=sqrt((double)dfs(n,1,1,8,8)/n-ave*ave);60 printf("%.3f\n", res);61 }62 return 0;63 }
POJ 1191 DP+DFS棋盘分割问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。