切蛋糕 Cake slicing

highkj · 2023-10-19 10:57:55 · 题解

更好的阅读体验。

前言

这道题是我与一位大佬一起做的，还是有一定的难度所以就决定发一篇题解纪念一下，但是不得不说这道题还是泰库啦！不过，TYX 小朋友还是太强啦！

思路

这道题其实和 这道题有一点类似那么我们就可以借用一下那一道题的思路了，我们可以用递归的方式来处理，就是每一次传进去这个要处理的矩阵的左上角和右下角，然后在统计出被包含的樱桃数量，如果为 0 那么就不合法，如果为 1 则代价为 0 然后，我们就可以枚举一下如何进行分割。

• 我们如果是以第 i 条横着的线进行分割的，那么代价就为 dp_{a,b,i,y}+dp_{i,b,x,y}+y-b 假设我们的左上角为 a,b 右下角为 x,y，这里我们因为是以线为分界边，那么我们的 i 是需要重合的。
• 我们若是竖着切也与横着切同理，这里就写一下代价方程为 dp_{a,b,x,i}+dp_{a,i,x,y}+x-a 其原理也与上述内容相同，所以不再赘述。

但是这里就有一个细节因为我们输入的 n,m 为格子的数量所以我们在传参是需要将 n,m 都加一，而且因为樱桃的下标是格子的下标所以我们对于一个樱桃被包含需要满足 yx<x，a\leq yx，yy<y，b\leq yy。

代码

#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rep1(i,x,y) for(int i=x;i>=y;i--)
#define fire signed
#define kong putchar(' ')
#define end putchar('\n')
#define in(x) scanf("%lld",&x)
#define lcm(x,y) x*y/__gcd(x,y)
#define w(x)  while(x--)
#define il inline
il void print(int x) {
    if(x>=10) print(x/10);
    putchar(x%10+'0');
}
int n,m;
struct chery{
    int x,y;
}ch[410];
int f[21][21][21][21] ;
int k;
bool cmp(chery a,chery b) {
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
int dfs(int a,int b,int x,int y) {
    if( f[a][b][x][y] < 0x3f3f3f3f / 2 ) return f[a][b][x][y] ;
    int cnt=false;
    rep(i,1,k) {
        if(ch[i].x>=a&&ch[i].x<x) {
            if(ch[i].y>=b&&ch[i].y<y){
                cnt ++ ; 
            }
        }
    }
    if(!cnt) return INT_MAX;
    if(cnt==1) return f[a][b][x][y] = false;
    rep(i,a+1,x-1) f[a][b][x][y] = min(f[a][b][x][y],dfs(a,b,i,y)+dfs(i,b,x,y)+y-b);
    rep(i,b+1,y-1) f[a][b][x][y] = min(f[a][b][x][y],dfs(a,b,x,i)+dfs(a,i,x,y)+x-a);
    return f[a][b][x][y];
}
int idx;
fire main() {
    while(cin>>n>>m>>k){
    memset(f,0x3f,sizeof f);
    rep(i,1,k) 
    {
        in(ch[i].x),in(ch[i].y);
    }
    sort(ch+1,ch+1+k,cmp);
    printf("Case %lld: ",++idx);
    cout<<dfs(1,1,n+1,m+1)<<endl;
}
//  cout << f[3][1][4][3] << endl ;
    return false;
}
/*
3 4 3 
1 2 
2 3 
3 2
3 4 3 1 2 2 3 3 2
*/