【bzoj1048】[HAOI2007]分割矩阵

2015.05.25 14:37 Mon | 18次阅读 | 旧日oi | 固定链接 | 源码

Description

将一个a*b的数字矩阵进行如下分割:将原矩阵沿某一条直线分割成两个矩阵,再将生成的两个矩阵继续如此分割(当然也可以只分割其中的一个),这样分割了(n-1)次后,原矩阵被分割成了n个矩阵。(每次分割都只能沿着数字间的缝隙进行)原矩阵中每一位置上有一个分值,一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成n个矩阵,并使各矩阵总分的均方差最小。请编程对给出的矩阵及n,求出均方差的最小值。
范围1<a,b<=10,n<=10
题解
想什么,直接爆搜!注意题目说的是均方差,我开始看错了,但是因为求平均数那步没用double,导致过了样例……

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 23333333333333333ll
int a,b,n;
double ave;
ll x[15][15],sum[15][15];
double dp[11][11][11][11][11];
double sqr(double x)
{
    return x*x;
}
ll get(int a,int b,int c,int d)
{
    return sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1];
}
double dfs(int x,int y,int xx,int yy,int ret)
{
    if(ret==0) return dp[x][y][xx][yy][0]=sqr(get(x,y,xx,yy)-ave);
    if(dp[x][y][xx][yy][ret]!=-1) return dp[x][y][xx][yy][ret];
    double ans=inf;
    for(int k=0;k<ret;k++)
    {
        for(int i=x+1;i<=xx;i++) 
        ans=min(ans,dfs(i,y,xx,yy,k)+dfs(x,y,i-1,yy,ret-1-k));
        for(int i=y;i<yy;i++)
        ans=min(ans,dfs(x,y,xx,i,k)+dfs(x,i+1,xx,yy,ret-1-k));
    }
    return dp[x][y][xx][yy][ret]=ans;
}
int main()
{
    cin>>a>>b>>n;
    for(int i=1;i<11;i++)
    for(int j=1;j<11;j++)
    for(int k=1;k<11;k++)
    for(int p=1;p<11;p++)
    for(int q=1;q<11;q++)
    dp[i][j][k][p][q]=-1;
    for(int i=1;i<=a;i++)
    for(int j=1;j<=b;j++)
    {
        scanf("%d",&x[i][j]);
        sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+x[i][j];
    }
    ave=1.0*sum[a][b]/n;
    printf("%.2lf\n",sqrt(dfs(1,1,a,b,n-1)/n));
}```