【poj 1191】盤分割問題解＆コード(C＋＋)

タイトルリンク:http://poj.org/problem?id=1191 問題解:この問題は黒い本にあり、ネット上の問題解も多く、彼らは分散の公式化に成功してS^2=(Σ(xi^2)/n-(x)^2になった.(sは分散、xiは分割されたi番目の矩形のスコア、nは矩形の個数、xは平均値)を加え、左上角が(x 1,y 1)、右下角が(x 2,y 2)の矩形がn個に分割されたときのs^2をdp[n][x 1][y 1][x 2][y 2]で表すと、最終的な答えはsqrt(dp[n][1][1][1][8][8])、この場合,上記の式dpによる遷移方程式も難しくないが,具体的にはコードを見てlong doubleを開くように注意すると,中間過程での操作で精度に誤りが生じる.
しかし、もう一つの方法は、上記の公式を通じて、依然としてdp[n][x 1][y 1][x 2][y 2]であるが、それが表す意味は変化しており、この方法は明らかに私の状態遷移よりも少しよく書かれており、具体的には黒い本を読んだり、他の人の問題解を読んだりしてもよい.コード:

#include
#include
#include
#include
#include
#include
using namespace std;
int n,f[10][10];
long double p[10][10][10][10];
long double dp[20][10][10][10][10];
long double sum[10][10][10][10];
int shu[10][10][10][10];
int add(int x1,int y1,int x2,int y2)
{
    int ans=0;
    for (int i=x1;i<=x2;i++)
    for (int j=y1;j<=y2;j++)
    ans+=f[i][j];
    return ans;
}
long double dfs(int x,int x1,int y1,int x2,int y2)
{
    if (dp[x][x1][y1][x2][y2]!=-1 )
    return dp[x][x1][y1][x2][y2];

    dp[x][x1][y1][x2][y2]=99999.9;
    if (x1for (int i=x1;ilong double t1=dfs(x-1,x1,y1,i,y2);
        long double t2=dfs(x-1,i+1,y1,x2,y2);
        long double h1=(t1+pow((sum[x1][y1][i][y2]/(x-1)),2))*(x-1);
                long double h2=(t2+pow((sum[i+1][y1][x2][y2]/(x-1)),2))*(x-1);
        long double a1=(h1+pow(sum[i+1][y1][x2][y2],2))/x-pow(sum[x1][y1][x2][y2]/x,2);
        long double a2=(h2+pow(sum[x1][y1][i][y2],2))/x-pow(sum[x1][y1][x2][y2]/x,2);
        dp[x][x1][y1][x2][y2]=min(dp[x][x1][y1][x2][y2],min(a1,a2));

    }

    if (y1for (int i=y1;ilong double t1=dfs(x-1,x1,y1,x2,i);
            long double t2=dfs(x-1,x1,i+1,x2,y2);
            long double h1=(t1+pow((sum[x1][y1][x2][i]/(x-1)),2))*(x-1);
                long double h2=(t2+pow((sum[x1][i+1][x2][y2]/(x-1)),2))*(x-1); 
        long double a2=(h2+pow(sum[x1][y1][x2][i],2))/x-pow(sum[x1][y1][x2][y2]/x,2);
        long double a1=(h1+pow(sum[x1][i+1][x2][y2],2))/x-pow(sum[x1][y1][x2][y2]/x,2);
        dp[x][x1][y1][x2][y2]=min(dp[x][x1][y1][x2][y2],min(a1,a2));
    }
    return dp[x][x1][y1][x2][y2];
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=8;i++)
    for (int j=1;j<=8;j++)
    scanf("%d",&f[i][j]);

    //S^2=(∑(xi^2))/n-(x)^2;
    for (int i=1;i<=20;i++)
    for (int j=1;j<=8;j++)
    for (int w=1;w<=8;w++)
    for (int k=1;k<=8;k++)
    for (int l=1;l<=8;l++)
    dp[i][j][w][k][l]=-1;

    for (int i=1;i<=8;i++)
    for (int j=1;j<=8;j++)
    for (int k=i;k<=8;k++)
    for (int w=j;w<=8;w++)
    {
        sum[i][j][k][w]=add(i,j,k,w);
        dp[1][i][j][k][w]=0;
    }
    long double hhh=sqrt(dfs(n,1,1,8,8));

    printf("%.3lf
",hhh);
}