神秘绑架案
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
冬马被方师傅绑架了！！！
一天，春希收到了一个信封，里面有一张印有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
3 | 1.633 |
Source
2014 UESTC Training for Dynamic Programming
解题报告
。。。这题最大的坑点在于题意。。(我悲剧的查了两小时的错，结果发现题读错了。。。）
注意到你切矩形一次，有一边就不能再切了！！！。。。
也就是说你每切一次，就只能选择其中的一边继续切(玩醉了)
记忆化搜索,f(i,j,k) 表示把坐上角序号为i ,右下角序号为j的矩形分成k块的最小(x - x_)^2值..
剩下的搜就是了（水题)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = ;
int sum[maxn][maxn],n;
double f[][][],average= .;
bool arrive[][][]; inline int getr(int x)
{
return (x-)/ + ;
} inline int getc(int x)
{
return (x-) % + ;
} inline int getid(int x,int y)
{
return (x-)*+y;
} double getval(int left,int right)
{
int sumx = ;
int rst = getr(left) , red = getr(right) , cst = getc(left) , ced = getc(right);
for(int i = rst ; i <= red ; ++ i)
sumx += sum[i][ced] - sum[i][cst-];
return (double)(sumx - average)*(sumx - average);
} double dp(int left,int right,int times)
{
if (arrive[left][right][times])
return f[left][right][times];
double &ans = f[left][right][times] = 1e110;
arrive[left][right][times] = true;
int rst = getr(left) , red = getr(right) , cst = getc(left) , ced = getc(right);
int number = (red - rst + ) * (ced - cst + );
if (times > number)
return ans;
if (times == ) //无法继续切割
return ans = getval(left,right);
//竖着切
for(int i = cst + ; i <= ced ; ++ i)
{
int newleft = getid(rst,i);
int newright = getid(red,i-);
ans = min(ans,getval(left,newright)+dp(newleft,right,times-)); //拿右边继续切
ans = min(ans,getval(newleft,right)+dp(left,newright,times-)); //拿左边继续切
}
//横着切
for(int i = rst ; i < red ; ++ i)
{
for(int j = ; j <= times- ; ++ j)
{
int newleft = getid(i+,cst);
int newright = getid(i,ced);
ans = min(ans,getval(left,newright)+dp(newleft,right,times-)); //拿下面继续切
ans = min(ans,getval(newleft,right)+dp(left,newright,times-)); //拿上面继续切
}
}
return ans;
} int main(int argc,char *argv[])
{
memset(sum,,sizeof(sum));
memset(arrive,false,sizeof(arrive));
scanf("%d",&n);
for(int i = ; i <= ; ++ i)
for(int j = ; j <= ; ++ j)
{
int temp;
scanf("%d",&temp);
sum[i][j] = sum[i][j-] + temp;
average += (double)temp;
}
average /= n;
printf("%.3f\n",sqrt(dp(,,n) / n));
return ;
}