【Link】:

【Description】



给你一个n*m的格子;

然后里面零零散散地放着葡萄

让你把它切成若干个小矩形方格

使得每个小矩形方格都恰好包含有一个葡萄.

要求切的长度最短;

问最短的切割距离;

【Solution】



记忆化搜索;

先枚举位点竖着切;

再枚举位点横着切

需要快速计算某个正方形内有多少个葡萄;

->前缀和;

每个dfs有5个参数;

x0,y0,x1,y1,cnt

左边4个参数,是当前切的这个矩形的左下角和右上角,以及这个矩形当前的葡萄个数;

输出dfs(1,1,n,m,k);



【NumberOf WA】



2



【Reviw】



一开始没有想到前缀和的统计方法。



【Code】

#include <bits/stdc++.h>

using namespace std;

const int K = 400;

const int N = 20;

const int INF = 0x3f3f3f3f;

int f[N+5][N+5][N+5][N+5];

int n,m,k;

int sum[N+5][N+5];

int cnt(int x0,int y0,int x1,int y1){

    int num = 0;

    num = sum[x1][y1]-sum[x1][y0-1]-sum[x0-1][y1]+sum[x0-1][y0-1];

    return num;

}

int dfs(int x0,int y0,int x1,int y1,int rest){

    if (f[x0][y0][x1][y1]!=-1) return f[x0][y0][x1][y1];

    if (rest==1) return f[x0][y0][x1][y1] = 0;

    int mi = INF;

    for (int i = y0;i <= y1-1;i++){

        /*

            left

            x1       (x1,i)  (x1,i+1) (x1,y1)

            x0,y0    (x0,i)  (x0,i+1) (x0,y1)

        */

        int numleft = cnt(x0,y0,x1,i),numright = cnt(x0,i+1,x1,y1);

        if (numleft>=1 && numright>=1){

            int temp1 = dfs(x0,y0,x1,i,numleft);

            int temp2 = dfs(x0,i+1,x1,y1,numright);

            mi = min(mi,temp1+temp2+x1-x0+1);

        }

    }

    for (int i = x0;i <= x1-1;i++){

        /*

            up

            x1,y0       x1,y1

            i+1,y0      i+1,y1

            down

            i,y0        i,y1

            x0,y0       x0,y1

        */

        int numup = cnt(i+1,y0,x1,y1),numdown = cnt(x0,y0,i,y1);

        if (numup>=1 && numdown>=1){

            int temp1 = dfs(i+1,y0,x1,y1,numup);

            int temp2 = dfs(x0,y0,i,y1,numdown);

            mi = min(mi,temp1+temp2+y1-y0+1);

        }

    }

    return f[x0][y0][x1][y1] = mi;

}

int main(){

    //freopen("F:\\rush.txt","r",stdin);

    int T = 0;

    while (~scanf("%d%d%d",&n,&m,&k)){

        T++;

        memset(f,-1,sizeof f);

        memset(sum,0,sizeof sum);

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

            int x,y;

            scanf("%d%d",&x,&y);

            sum[x][y]++;

        }

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

            for (int j = 1;j <= m;j++)

                sum[i][j] = sum[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];

        printf("Case %d: %d\n",T,dfs(1,1,n,m,k));

    }

    return 0;

}