poj1191棋盘分割(动态规划)

9月 16

黑书上面动态规划篇的第二道例题，题目大意很简单，可以记忆化搜索或dp做。最近在训练dp，直接dp做了，但记忆化搜索更简单。黑书上面的动态规划转移方程也写得很简单，用五层for循环嵌套。我的方程和他的略有不同，但大体意思是一样的！

$dp_{kx_{1}y_{1}x_{2}y_{2}}$为下列式子中最小的一个

$dp_{(k-1)x_{1}y_{1}ay_{2}} + dp_{0(a+1)y_{1}x_{2}y_{2}}$ 其中$x_{1}≤a﹤x_{2}$
$dp_{(k-1)(a+1)y_{1}x_{2}y_{2}} + dp_{0x_{1}y_{1}ay_{2}}$ 其中$x_{1}≤a﹤x_{2}$
$dp_{(k-1)x_{1}y_{1}x_{2}a} + dp_{0x_{1}(a+1)x_{2}y_{2}}$ 其中$y_{1}≤a﹤y_{2}$
$dp_{(k-1)x_{1}(a+1)x_{2}y_{2}} + dp_{0x_{1}y_{1}x_{2}a}$ 其中$y_{1}≤a﹤y_{2}$

然后就是5个嵌套的for循环，这题还有一个问题，不知道为什么，我之前用int和__int64都wa了，改成long double才ac了，难道卡在精度上？

poj1191 棋盘分割view raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))

int a[10][10];
int sum[10][10];
long double dp[20][10][10][10][10];
long double count(int x,int y,int m,int n)
{
	long double ans= __int64(sum[m][n]-sum[m][y]-sum[x][n]+sum[x][y]);
	return ans*ans;
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int i,j,k;
		zero(sum);
		int num=0;
		for(i=1;i<=8;i++)
		{
			for(j=1;j<=8;j++)
			{
				scanf("%d",&a[i][j]);
				sum[i][j]=sum[i-1][j]-sum[i-1][j-1]+sum[i][j-1]+a[i][j];
				num+=a[i][j];
			}
		}
		int x,y;
		for(i=1;i<=8;i++)
			for(j=1;j<=8;j++)
				for(x=i;x<=8;x++)
					for(y=j;y<=8;y++)
						dp[0][i][j][x][y]=count(i-1,j-1,x,y);	
		for(k=1;k<n;k++)
		{
			for(i=0;i<=8;i++)
			{
				for(j=0;j<=8;j++)
				{
					for(x=1;x+i<=8;x++)
					{
						for(y=1;y+j<=8;y++)
						{

							int t;
							dp[k][x][y][x+i][y+j]=long double((1)<<30);
							for(t=x;t<x+i;t++)
							{
								dp[k][x][y][x+i][y+j]=min(dp[k][x][y][x+i][y+j],dp[k-1][t+1][y][x+i][y+j]+dp[0][x][y][t][y+j]);
								dp[k][x][y][x+i][y+j]=min(dp[k][x][y][x+i][y+j],dp[k-1][x][y][t][y+j]+dp[0][t+1][y][x+i][y+j]);
							}
							for(t=y;t<y+j;t++)
							{
								dp[k][x][y][x+i][y+j]=min(dp[k][x][y][x+i][y+j],dp[k-1][x][y][x+i][t]+dp[0][x][t+1][x+i][y+j]);
								dp[k][x][y][x+i][y+j]=min(dp[k][x][y][x+i][y+j],dp[k-1][x][t+1][x+i][y+j]+dp[0][x][y][x+i][t]);
							}
						}
					}
				}
			}
		}
		long double ans=1.0*dp[n-1][1][1][8][8]/n-long double(1.0*num/n)*long double(1.0*num/n);
		printf("%.3lf\n",sqrt(ans));
	}
    return 0;
}