POJ1191 棋盘分割记忆化搜索

　　化简公式，然后记忆化搜索求解。a=sqrt( Σ(xi-x)^2/n ) => n*a^2=(x1-x)^2 + (x2-x)^2 + ...... + (xn-x)^2 => n*a^2=(x1^2+x2^2+......+xn^2) - 2*(x1+x2+......xn)*x + n*x^2 . 可以看出就是求分割后平方和的最小值，然后记忆化搜索就可以了，f[k][x1][y1][x2][y2]为方块(x1,y2)-(x2,y2)还需分割k次后的平方和的最小值。这里可以先求出所有方块的平方和值，使得在搜索过程中求任意方块O(1)。看一下时间复杂度上限，一共有8^4方块，每个方块最多被分割n次，最多被2*8次更新，则O(8^5*n)，所以直接循环枚举都能过，但用忆化搜索可以去掉许多不必要的状态。

 1 //STATUS:C++_AC_0MS_592KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<algorithm>
 7 #include<string>
 8 #include<queue>
 9 #include<stack>
10 #include<vector>
11 #include<map>
12 using namespace std;
13 #define LL __int64
14 #define pii pair<int,int>
15 #define Max(a,b) ((a)>(b)?(a):(b))
16 #define Min(a,b) ((a)<(b)?(a):(b))
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 #define abs(a) ((a)>0?(a):-(a))
21 const int N=9,INF=0x3f3f3f3f;
22 
23 int num[N][N],f[15][N][N][N][N],sv[N][N][N][N],s[N][N];
24 int n;
25 
26 void getsv()
27 {
28     int i,j,t,x1,y1,x2,y2;
29     for(i=1;i<=8;i++){
30         for(j=1,t=0;j<=8;j++){
31             t+=num[i][j];
32             s[i][j]+=s[i-1][j]+t;
33         }
34     }
35     for(x1=1;x1<=8;x1++)
36         for(y1=1;y1<=8;y1++)
37             for(x2=x1;x2<=8;x2++)
38                 for(y2=y1;y2<=8;y2++){
39                     sv[x1][y1][x2][y2]=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
40                     sv[x1][y1][x2][y2]*=sv[x1][y1][x2][y2];
41                 }
42 }
43 
44 int dfs(int x1,int y1,int x2,int y2,int cur)
45 {
46     if(cur==1)return sv[x1][y1][x2][y2];
47     int& d=f[cur][x1][y1][x2][y2];
48     if(d!=INF)return d;
49     if( x2-x1+y2-y1<cur )return INF;
50     int i;
51     for(i=y1+1;i<=y2;i++){
52         d=Min(d,dfs(x1,y1,x2,i-1,cur-1)+sv[x1][i][x2][y2]);
53         d=Min(d,dfs(x1,i,x2,y2,cur-1)+sv[x1][y1][x2][i-1]);
54     }
55     for(i=x1+1;i<=x2;i++){
56         d=Min(d,dfs(x1,y1,i-1,y2,cur-1)+sv[i][y1][x2][y2]);
57         d=Min(d,dfs(i,y1,x2,y2,cur-1)+sv[x1][y1][i-1][y2]);
58     }
59     return d;
60 }
61 
62 int main()
63 {
64  //   freopen("in.txt","r",stdin);
65     int i,j,sum=0,x1,y1,x2,y2;;
66     double aver=0;
67     mem(f,INF);
68     scanf("%d",&n);
69     for(i=1;i<=8;i++)
70         for(j=1;j<=8;j++){
71             scanf("%d",&num[i][j]);
72             sum+=num[i][j];
73         }
74     aver=(double)sum/n;
75     getsv();
76     dfs(1,1,8,8,n);
77 
78     printf("%.3lf\n",sqrt((f[n][1][1][8][8]-2*sum*aver)/n+aver*aver) );
79     return 0;
80 }

POJ1191 棋盘分割 记忆化搜索

POJ1191 棋盘分割记忆化搜索