POJ1191棋盘分割

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

1.分析式子！！！

　　发现xba是定值，σ的大小仅和∑ xi^2 有关。故dp条件是平方和最小。

2.分出一块就像割掉一条，只需枚举从四个方向割+割多宽。

（赋初值之小优美）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int n,a,sum[][],sm[],ss,d[][][][][];

bool vis[][][][][];

double xba,ans;

int summ(int x1,int y1,int x2,int y2)

{

    int s=sum[x2][y2]-sum[x1-][y2]-sum[x2][y1-]+sum[x1-][y1-];

    return s*s;

}

int dfs(int x1,int y1,int x2,int y2,int k)

{

    if(vis[x1][y1][x2][y2][k])return d[x1][y1][x2][y2][k];

    vis[x1][y1][x2][y2][k]=;

    if(k==)return d[x1][y1][x2][y2][k]=summ(x1,y1,x2,y2);

    for(int i=x1;i<x2;i++)

        d[x1][y1][x2][y2][k]=min(d[x1][y1][x2][y2][k],

            min(dfs(i+,y1,x2,y2,k-)+summ(x1,y1,i,y2),dfs(x1,y1,i,y2,k-)+summ(i+,y1,x2,y2)));

    for(int i=y1;i<y2;i++)

        d[x1][y1][x2][y2][k]=min(d[x1][y1][x2][y2][k],

            min(dfs(x1,i+,x2,y2,k-)+summ(x1,y1,x2,i),dfs(x1,y1,x2,i,k-)+summ(x1,i+,x2,y2)));

    return d[x1][y1][x2][y2][k];

}

int main()

{

    scanf("%d",&n);

    memset(d,,sizeof d);

    for(int i=;i<=;i++)

    {

        ss=;

        for(int j=;j<=;j++)

        {

            scanf("%d",&a);

            sm[j]+=a;

            ss+=sm[j];

            sum[i][j]=ss;

        }

    }

    dfs(,,,,n);

    xba=sum[][]/(n*1.0);

    ans=d[][][][][n]+xba*xba*n-*xba*sum[][];

    ans=sqrt(ans/n);

    printf("%.3lf",ans);

    return ;

}