poj 1191 矩形块的划分

时间：2023-01-10 08:19:50

思路：黑书的例题

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdio>

#define Maxn 20

#define mul(a) ((a)*(a))

using namespace std;

int dp[][][][][];

int s[][],val[][];

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

{

    return mul(s[x2][y2]-s[x2][y1-]-s[x1-][y2]+s[x1-][y1-]);

}

int main()

{

    int n,m,i,j;

    double avg;

    while(scanf("%d",&n)!=EOF)

    {

        memset(dp,,sizeof(dp));

        memset(s,,sizeof(s));

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

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

            scanf("%d",&val[i][j]);

            s[i][j]=s[i-][j]+s[i][j-]-s[i-][j-]+val[i][j];

        }

        int x1,y1,x2,y2;

        for(x1=;x1<=;x1++)

        for(y1=;y1<=;y1++)

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

        for(y2=y1;y2<=;y2++){

            dp[][x1][y1][x2][y2]=S(x1,y1,x2,y2);

        }

        int a,b;

        for(i=;i<=n-;i++)

        for(x1=;x1>=;x1--)

        for(y1=;y1>=;y1--)

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

        for(y2=y1;y2<=;y2++){

            int temp;

            for(a=x1;a<x2;a++){

            temp=min(dp[i-][x1][y1][a][y2]+S(a+,y1,x2,y2),dp[i-][a+][y1][x2][y2]+S(x1,y1,a,y2));

            dp[i][x1][y1][x2][y2]=min(temp,dp[i][x1][y1][x2][y2]);

            }

            for(b=y1;b<y2;b++){

            temp=min(dp[i-][x1][y1][x2][b]+S(x1,b+,x2,y2),dp[i-][x1][b+][x2][y2]+S(x1,y1,x2,b));

            dp[i][x1][y1][x2][y2]=min(dp[i][x1][y1][x2][y2],temp);

            }

        }

        double ans;

        avg=s[][]*1.0/(n*1.0);

        ans=(double)dp[n-][][][][];

        ans=ans/(n*1.0);

        ans-=avg*avg;

        printf("%.3lf\n",sqrt(ans));

    }

    return ;

}

相关文章