题目链接：

 

题意：一个矩形蛋糕上有好多个樱桃，现在要做的就是切割最少的距离，切出矩形形状的小蛋糕，让每个蛋糕上都有一个樱桃~问最少切割距离是？

 

分析：可以根据每次的切割范围遍历找最优值，也就是说状态描述d[u][d][l][r] 是这个范围内的最短距离。要是这个范围内只有一个樱桃，那么就是 0 ，要是没有樱桃就是无穷大。

 

1 #include 
     
       2  3 using namespace std; 4  5 const int INF = 0x3f3f3f3f; 6  7 bool maps[25][25]; 8 int r,c,cnt; 9 10 int dps[25][25][25][25];11 12 int sum(int u,int d,int l,int r)13 {14     int sums = 0;15     for(int i=u; i<=d; i++)16         for(int j=l; j<=r; j++)17             if(maps[i][j])18                 sums++;19     return sums;20 }21 22 int dp(int u,int d,int l,int r)23 {24     int &ans = dps[u][d][l][r];25     if(ans!=-1)26         return ans;27     else if(sum(u,d,l,r)==1)28         return ans=0;29     else if(sum(u,d,l,r)==0)30         return ans=INF;31     else32     {33         ans = INF;34         for(int i=u; i<=d; i++)35             ans = min(ans,dp(u,i,l,r)+dp(i+1,d,l,r)+r-l+1);36         for(int i=l; i<=r; i++)37             ans = min(ans,dp(u,d,l,i)+dp(u,d,i+1,r)+d-u+1);38     }39     return ans;40 }41 42 int main()43 {44     int kase = 1;45     while(scanf("%d%d%d",&r,&c,&cnt)!=EOF)46     {47         memset(dps,-1,sizeof(dps));48         memset(maps,0,sizeof(maps));49 50 51         for(int i=0; i