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]);
    }
}