POJ 1191 棋盘分割(DP)

题目链接

大体思路看,黑书。。。其他就是注意搞一个in数组,这样记忆化搜索,貌似比较快。

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
#define INF 0x7fffffff
int p[][],sum[][];
double dp[][][][][];
int in[][][][][];
double s[][][][];
int dfs(int x1,int y1,int x2,int y2,int k)
{
int i;
if(in[x1][y1][x2][y2][k])
return dp[x1][y1][x2][y2][k];
if(k == )
{
in[x1][y1][x2][y2][k] = ;
return dp[x1][y1][x2][y2][k] = s[x1][y1][x2][y2];
}
else
{
double minz = INF;
for(i = x1;i < x2;i ++)
{
minz = min(dfs(x1,y1,i,y2,k-)+s[i+][y1][x2][y2],minz);
minz = min(dfs(i+,y1,x2,y2,k-)+s[x1][y1][i][y2],minz);
}
for(i = y1;i < y2;i ++)
{
minz = min(dfs(x1,y1,x2,i,k-)+s[x1][i+][x2][y2],minz);
minz = min(dfs(x1,i+,x2,y2,k-)+s[x1][y1][x2][i],minz);
}
in[x1][y1][x2][y2][k] = ;
return dp[x1][y1][x2][y2][k] = minz;
}
}
int main()
{
int i,j,k,u,v,n,temp;
scanf("%d",&n);
temp = ;
for(i = ;i <= ;i ++)
{
for(j = ;j <= ;j ++)
{
scanf("%d",&p[i][j]);
temp += p[i][j];
}
}
for(i = ;i <= ;i ++)
{
for(j = ;j <= ;j ++)
{
for(k = ;k <= ;k ++)
{
for(u = ;u <= ;u ++)
{
for(v = ;v <= n;v ++)
dp[i][j][k][u][v] = INF;
}
}
}
}
for(i = ;i <= ;i ++)
{
for(j = ;j <= ;j ++)
sum[i][j] = sum[i-][j] + sum[i][j-] - sum[i-][j-] + p[i][j];
}
for(i = ;i <= ;i ++)
{
for(j = ;j <= ;j ++)
{
for(k = ;k <= ;k ++)
{
for(u = ;u <= ;u ++)
{
s[i][j][k][u] = sum[k][u]+sum[i-][j-]-sum[i-][u]-sum[k][j-];
s[i][j][k][u] *= s[i][j][k][u];
}
}
}
}
printf("%.3f\n",sqrt(dfs(,,,,n)*1.0/n-(temp*1.0/n)*(temp*1.0/n)));
return ;
}
上一篇:intial-scale=1的含义


下一篇:[翻译] UCZProgressView