习题9-3 UVA1629(dp)

Cake Slicing

题意：有一个n行m列的网格上有一些黑点，要求进行切割，使最后每块上只有一个黑点，求最少的刀数

思路：记忆化搜索，枚举每一条边来切，每一次搜索自己所能切割的所有情况取最小值

但是TL，纠结了一下，发现明明2个for(横+竖)就能切出来，硬是被我写成了n^2
的，自己好坑- -

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

const int maxn = 25;

int tmap[maxn][maxn];

int G[maxn][maxn][maxn][maxn];

int dfs(int l1,int l2,int r1,int r2)

{

    int num = 0;

    if(G[l1][l2][r1][r2] != -1)

        return G[l1][l2][r1][r2];

    for(int i = l1; i <= l2; i++)

        for(int j = r1; j <= r2; j++)

        {

            if(tmap[i][j])

                num ++;

        }

    if(num == 1)

        return G[l1][l2][r1][r2]=0;

    if(num == 0)

        return G[l1][l2][r1][r2] = 10000;

    int ans = 0x3f3f3f3f;

    int tans= 0x3f3f3f3f;

    for(int i = l1; i<= l2; i++)

    {

        if(i + 1 <= l2)

        {

            ans = r2-r1+1;

            ans += dfs(l1,i,r1,r2);

            ans += dfs(i+1,l2,r1,r2);

            tans = min(ans,tans);

        }

    }

    for(int j = r1; j <=r2; j++)

    {

        if(j + 1 <= r2)

        {

            ans = l2-l1+1;

            ans +=dfs(l1,l2,r1,j);

            ans += dfs(l1,l2,j+1,r2);

            tans = min(ans,tans);

        }

    }

    return G[l1][l2][r1][r2] = tans ;

}

int main()

{

    int n,m,k;

    int a,b;

    int cas = 1;

    while(scanf("%d%d%d",&n,&m,&k) != EOF)

    {

        memset(tmap,0,sizeof(tmap));

        memset(G,-1,sizeof(G));

        for(int i = 1; i <= k; i++)

        {

            scanf("%d%d",&a,&b);

            tmap[a][b] = 1;

        }

        printf("Case %d: %d\n",cas++,dfs(1,n,1,m));

    }

    return 0;

}