暑假集训Day12 A (棋盘dp 记忆化搜索)

题目链接在这里：​​Problem - A - Codeforces​​

这是一类棋盘问题，数据范围很小，可以考虑爆搜。由于上下左右四个边界都是在动的，所以在搜索的时候要把四个边界都当成参数。为了剪枝需要记忆化一下，注意记忆化数组的初值不能赋为0，应该赋为-1

1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=55;
 4 int n,an[MAX][MAX][MAX][MAX];
 5 char s[MAX][MAX];
 6 int dfs(int x,int y,int z,int w){
 7     if (x==y && z==w) {
 8         if (s[x][z]=='#')
 9             an[x][y][z][w]=1;
10         else 
11             an[x][y][z][w]=0;
12         return an[x][y][z][w];
13     }
14     if (an[x][y][z][w]!=-1) return an[x][y][z][w];
15     int i,j,ans;
16     ans=max(y-x+1,w-z+1);//cout<<ans<<endl;
17     for (i=x;i<y;i++) ans=min(ans,dfs(x,i,z,w)+dfs(i+1,y,z,w));
18     for (i=z;i<w;i++) ans=min(ans,dfs(x,y,z,i)+dfs(x,y,i+1,w));
19     //cout<<x<<' '<<y<<' '<<z<<' '<<w<<' '<<ans<<endl;
20     an[x][y][z][w]=ans;
21     return ans;
22 }
23 int main(){
24     freopen ("a.in","r",stdin);
25     freopen ("a.out","w",stdout);
26     int i,j,low,high,mid;
27     scanf("%d",&n);
28     for (i=1;i<=n;i++)
29         scanf("%s",s[i]+1);
30     low=0,high=n;
31     memset(an,-1,sizeof(an));
32     printf("%d",dfs(1,n,1,n));
33     return 0;
34 }