BZOJ1048 [HAOI2007]分割矩阵

题面

http://www.lydsy.com/JudgeOnline/problem.php?id=1048

题解

img

而题目求标准差,要sqrtsqrt一下。

考虑预处理出前缀和,这样可以O(1)算内部数值

f[i][j][k][l][m]f[i][j][k][l][m]表示左上角是[i][j][i][j],右下角是[k][l][k][l],当前这一个弄成m个矩形,最小的方差是多少。

记忆化DFS即可。

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
namespace IO{
#define getch getchar
LL read(){LL T = 0,f = 1;char c = getch();while ((c<'0'||c>'9')&&c!='-') c=getch();if(c=='-')f=-1,c=getch();while (c>='0'&&c<='9'){T=((T<<1)+(T<<3))+c-48;c=getch();}return T*f;}
inline void write(LL x){if(x < 0) putchar('0'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
};
#define pc putchar
using namespace IO;
double f[15][15][15][15][15];
double s[15][15];
int a,b,n;
double ave;
double dfs(int a,int b,int c,int d,int e){
double &res = f[a][b][c][d][e];
if (res != -1) return res;
double sum = s[c][d] - s[c][b-1] - s[a-1][d] + s[a-1][b-1];
// printf("[%d,%d][%d,%d] %lf\n",a,b,c,d,sum);
if (e == 1) return res = (sum - ave) * (sum - ave);
res = 1e10;
for (int i=a;i<c;i++)
for (int k=1;k<e;k++)
res = min(res,dfs(a,b,i,d,k) + dfs(i+1,b,c,d,e-k));
for (int i=b;i<d;i++)
for (int k=1;k<e;k++)
res = min(res,dfs(a,b,c,i,k) + dfs(a,i+1,c,d,e-k));
return res;
}
#define rep(i,a,b) for(int i=a;i<=b;i++)
int main(){
a = read(),b = read(),n = read();
memset(s,0,sizeof(s));
for (int i=1;i<=a;i++)
for (int j=1;j<=b;j++)
s[i][j] = read() + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
rep(i,0,11)rep(j,0,11)rep(k,0,11)rep(l,0,11)rep(m,0,11) f[i][j][k][l][m] = -1;
ave = (double)s[a][b] / n;
printf("%.2lf\n",sqrt(dfs(1,1,a,b,n) / n));
return 0;
}
文章目录
  1. 1. 题面
  2. 2. 题解