hdu2513:Cake slicing（记忆化搜索）

             题目链接：点击打开链接

             题目大意：

                    给你一块n*m的蛋糕，上面有k个樱桃，问你怎么切才能使得每个蛋糕块上只有一个樱桃并且保证你切的长度最小，输出最小长度

             题意解析：

                    刚开始的时候是在无从下手，根本不知道从哪开始写，后来看了别人的题解，又是四维dp，而且是记忆化搜索，老实说到现在还是有点搞不清楚什么时候该有记忆               化什么时候用递推。

                    知道记忆化后就是用一个dp数组，dp[i][j][p][q]表示已(i,j)为左上角(p,q)为右下角的蛋糕分割为目标状态需要切割的最小长度。至于怎么实现，暴力从左到右和从上到                下扫一遍即可。

                    此处有一点小坑，导致我hdu虽然ac了但是在我们学校的contest里一直wa（应该是挂的uva的题），百思不得其解，最后找别人ac代码发现确实是有些问题，可能              hdu数据不太严谨。。。坑点就在于每次对于一个蛋糕块，会先搜索它上面的樱桃个数，我原来的代码写的是当个数<=1的时候return 0;后来hduac以后contest一直wa，后            来发现别人代码是分了情况的，当樱桃数为0就返回INF（也就是一个极大值），为1返回0，想想可能确实是自己原来的代码存在漏洞，唉，还是要继续学习。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#define next ne
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,k;
int a[25][25];
int dp[25][25][25][25];
int dfs(int i,int j,int p,int q)
{
    if(dp[i][j][p][q]!=-1)
        return dp[i][j][p][q];
    else
    {
        int cnt=0;             //找当前蛋糕块上樱桃的个数
        for(int s=i;s<=p;s++)
        {
            for(int b=j;b<=q;b++)
            {
                if(a[s][b]==1)
                    cnt++;
            }
        }
        if(cnt==0)          //分情况讨论,不然可能会wa
            return dp[i][j][p][q]=INF;
        if(cnt==1)
            return dp[i][j][p][q]=0;
        int ans=INF;
        for(int s=i;s<p;s++)        //从左到右从上到下依次暴搜一遍,遍历寻找最小值
            ans=min(ans,dfs(i,j,s,q)+dfs(s+1,j,p,q)+(q-j+1));
        for(int s=j;s<q;s++)
            ans=min(ans,dfs(i,j,p,s)+dfs(i,s+1,p,q)+(p-i+1));
        return dp[i][j][p][q]=ans;
    }
}
int main()
{
    int kase=0;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        int f1,f2;
        kase++;
        memset(dp,-1,sizeof(dp));
        memset(a,0,sizeof(a));
        for(int f=0;f<k;f++)
        {
            scanf("%d%d",&f1,&f2);
            a[f1][f2]=1;
        }
        dfs(1,1,n,m);
        printf("Case %d: %d\n",kase,dp[1][1][n][m]);
    }
}