poj1191棋盘分割——区间DP

题目：http://poj.org/problem?id=1191

分析题意，可知每次要沿棋盘中的一条线把一块一分为二，取其中一块继续分割；

σ最小经分析可知即为每块的xi和的平方最小；

故用区间DP，用dfs搜出最小值即可。

代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,a,s[10][10],dp[10][10][10][10][20];
double arg,ans,sum;
bool vis[10][10][10][10][20];//
//int p(int x1,int x2,int y1,int y2)//!!!
int p(int x1,int y1,int x2,int y2)
{
int sm=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
return sm*sm;
}
int dfs(int x1,int y1,int x2,int y2,int k)
{
if(vis[x1][y1][x2][y2][k])return dp[x1][y1][x2][y2][k];
vis[x1][y1][x2][y2][k]=1;
if(k==1)return dp[x1][y1][x2][y2][k]=p(x1,y1,x2,y2);//!
for(int i=x1+1;i<=x2;i++)
dp[x1][y1][x2][y2][k]=min(dp[x1][y1][x2][y2][k],
min(dfs(i,y1,x2,y2,k-1)+p(x1,y1,i-1,y2),p(i,y1,x2,y2)+dfs(x1,y1,i-1,y2,k-1)));
for(int i=y1+1;i<=y2;i++)
dp[x1][y1][x2][y2][k]=min(dp[x1][y1][x2][y2][k],
min(dfs(x1,i,x2,y2,k-1)+p(x1,y1,x2,i-1),p(x1,i,x2,y2)+dfs(x1,y1,x2,i-1,k-1)));
return dp[x1][y1][x2][y2][k];
}
int main()
{
scanf("%d",&n);
memset(dp,11,sizeof dp);
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
{
scanf("%d",&a);
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a;
}
arg=s[8][8]/(n*1.0);
dfs(1,1,8,8,n);
ans=dp[1][1][8][8][n]+n*arg*arg-2*arg*s[8][8];
ans=sqrt(ans/n);
printf("%.3lf",ans);
return 0;
}