神秘绑架案
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
冬马被方师傅绑架了！！！
一天，春希收到了一个信封，里面有一张印有8×8棋盘的纸，一个被加了密的U盘和一个便条。便条上写着：
冬马在我手上，如果你想救出冬马，U盘里就有我详细的地址，当然前提是你能解出密码！
你可以把这个棋盘分割成n块，每一次你可以从一棋盘上割下一块矩形，并让剩下的部分也是矩形，再将剩下的部分如此分割。
原棋盘每一格有一个分值，一块矩形的总分为其所含各格分值之和。你需要按上述方法将棋盘分成n块后，求出各矩形棋盘总分的均方差。我也不介意告诉你，所有均方差中的最小值就是U盘的密码，那么请挣扎吧！
平均数公式：
x¯=∑ni=1xin
均方差公式：
σ=∑ni=1(xi−x¯)2n−−−−−−−−−−−−√
------方师傅留
春希非常焦急的找到了你，希望你能找出这个最小值，救出冬马。
Input
第一行一个整数n，表示分割后的块数。(1<n<15)
第二行到第九行，每行八个小于100的非负整数，表示棋盘上相应格子的分值。
Output
一个数，表示求出的最小值。(四舍五入精确到小数点后三位)
Sample input and output
| Sample Input | Sample Output |
|---|---|
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 3 |
1.633 |
Source
2014 UESTC Training for Dynamic Programming
解题报告
。。。这题最大的坑点在于题意。。(我悲剧的查了两小时的错，结果发现题读错了。。。）
注意到你切矩形一次，有一边就不能再切了！！！。。。
也就是说你每切一次，就只能选择其中的一边继续切(玩醉了)
记忆化搜索,f(i,j,k) 表示把坐上角序号为i ,右下角序号为j的矩形分成k块的最小(x - x_)^2值..
剩下的搜就是了（水题)
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 const int maxn = 10; 8 int sum[maxn][maxn],n; 9 double f[70][70][20],average= 0.; 10 bool arrive[70][70][20]; 11 12 inline int getr(int x) 13 { 14 return (x-1)/8 + 1; 15 } 16 17 inline int getc(int x) 18 { 19 return (x-1) % 8 + 1; 20 } 21 22 23 inline int getid(int x,int y) 24 { 25 return (x-1)*8+y; 26 } 27 28 29 double getval(int left,int right) 30 { 31 int sumx = 0 ; 32 int rst = getr(left) , red = getr(right) , cst = getc(left) , ced = getc(right); 33 for(int i = rst ; i <= red ; ++ i) 34 sumx += sum[i][ced] - sum[i][cst-1]; 35 return (double)(sumx - average)*(sumx - average); 36 } 37 38 double dp(int left,int right,int times) 39 { 40 if (arrive[left][right][times]) 41 return f[left][right][times]; 42 double &ans = f[left][right][times] = 1e110; 43 arrive[left][right][times] = true; 44 int rst = getr(left) , red = getr(right) , cst = getc(left) , ced = getc(right); 45 int number = (red - rst + 1) * (ced - cst + 1); 46 if (times > number) 47 return ans; 48 if (times == 1) //无法继续切割 49 return ans = getval(left,right); 50 //竖着切 51 for(int i = cst + 1 ; i <= ced ; ++ i) 52 { 53 int newleft = getid(rst,i); 54 int newright = getid(red,i-1); 55 ans = min(ans,getval(left,newright)+dp(newleft,right,times-1)); //拿右边继续切 56 ans = min(ans,getval(newleft,right)+dp(left,newright,times-1)); //拿左边继续切 57 } 58 //横着切 59 for(int i = rst ; i < red ; ++ i) 60 { 61 for(int j = 1 ; j <= times-1 ; ++ j) 62 { 63 int newleft = getid(i+1,cst); 64 int newright = getid(i,ced); 65 ans = min(ans,getval(left,newright)+dp(newleft,right,times-1)); //拿下面继续切 66 ans = min(ans,getval(newleft,right)+dp(left,newright,times-1)); //拿上面继续切 67 } 68 } 69 return ans; 70 } 71 72 73 74 int main(int argc,char *argv[]) 75 { 76 memset(sum,0,sizeof(sum)); 77 memset(arrive,false,sizeof(arrive)); 78 scanf("%d",&n); 79 for(int i = 1 ; i <= 8 ; ++ i) 80 for(int j = 1 ; j <= 8 ; ++ j) 81 { 82 int temp; 83 scanf("%d",&temp); 84 sum[i][j] = sum[i][j-1] + temp; 85 average += (double)temp; 86 } 87 average /= n; 88 printf("%.3f ",sqrt(dp(1,64,n) / n)); 89 return 0; 90 }