「BZOJ1048」[HAOI2007] 分割矩阵
Description
将一个a*b的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两个矩阵继续如此分割（当然也可以只分割其中的一个），这样分割了（n-1)次后，原矩阵被分割成了n个矩阵。（每次分割都只能沿着数字间的缝隙进行）原矩阵中每一位置上有一个分值，一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成n个矩阵，并使各矩阵总分的均方差最小。请编程对给出的矩阵及n，求出均方差的最小值。
Input
第一行为3个整数，表示a,b,n(1
Output
仅一个数，为均方差的最小值（四舍五入精确到小数点后2位）
Sample Input
5 4 4
2 3 4 6
5 7 5 1
10 4 0 5
2 0 2 3
4 1 1 1
2 3 4 6
5 7 5 1
10 4 0 5
2 0 2 3
4 1 1 1
Sample Output
0.50
题解
由于范围小，平均值一开始就能求出，所以记忆化搜索即可
顺便再用下二维前缀和
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,K; double ave; int a[15][15]; int s[15][15]; double t[15][15][15][15][15]; double dfs(int a,int b,int c,int d,int k) { double &res=t[a][b][c][d][k]; if(res!=-1)return res; if(k==0) { res=s[b][d]+s[a-1][c-1]-s[a-1][d]-s[b][c-1]; res=(res-ave)*(res-ave); return res; } res=1e9; for(int i=a+1;i<=b;i++) for(int j=0;j<k;j++) res=min(res,dfs(a,i-1,c,d,j)+dfs(i,b,c,d,k-j-1)); for(int i=c+1;i<=d;i++) for(int j=0;j<k;j++) res=min(res,dfs(a,b,c,i-1,j)+dfs(a,b,i,d,k-j-1)); return res; } int main() { n=read();m=read();K=read(); for(int a=0;a<=10;a++) for(int b=0;b<=10;b++) for(int c=0;c<=10;c++) for(int d=0;d<=10;d++) for(int l=0;l<=10;l++) t[a][b][c][d][l]=-1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j], ave=(double)s[n][m]/K; dfs(1,n,1,m,K-1); printf("%.2lf",sqrt(t[1][n][1][m][K-1]/K)); return 0; } |
Subscribe
计数器 9863456
OI 课件=>
OI 课件=>