翻译：有一个n行m列(1<=n,m<=20)的网络蛋糕上有k个樱桃。每次可以用一刀沿着网络线把蛋糕切成两块，并且只能够直切不能拐弯。要求最后每一块蛋糕上恰好有一个樱桃，且切割线总长度最小。
输入输出格式 输入格式:每次输入有若干组数据。每组数据第一行有三个正整数n m k(行，列，樱桃个数)，之后的k行每行两个正整数(樱桃的坐标) 输出格式:输出有若干行，对应每组数据。每行输出两个正整数(id,最小的切割长度)
输入输出样例 输入样例: 3 4 3 1 2 2 3 3 2 输出样例: Case 1: 5
dp[x][y][x1][y1]表示以x，y为上界，x1，y1为下界的最优解
转移的话直接枚举切割点
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; const int maxn = 25; int n,m,k,sum[maxn][maxn],mp[maxn][maxn],f[maxn][maxn][maxn][maxn]; int kase = 0; int getsum(int x,int y,int x1,int y1) { return sum[x1][y1]-sum[x1][y-1]-sum[x-1][y1]+sum[x-1][y-1]; } int dp(int x,int y,int x1,int y1) { int s=getsum(x,y,x1,y1);//得到范围内的樱桃个数，用前缀和实现 if(s==0) return inf;//不合法 if(s==1) return 0;//不用再切 int& ans = f[x][y][x1][y1]; if(ans!=inf) return ans; for(int i=x;i<x1;i++) { ans=min(ans,dp(x,y,i,y1)+dp(i+1,y,x1,y1)+y1-y+1); } for(int i=y;i<y1;i++) { ans=min(ans,dp(x,y,x1,i)+dp(x,i+1,x1,y1)+x1-x+1); } return ans; } int main() { while(scanf("%d%d%d",&n,&m,&k)!=EOF) { memset(sum,0,sizeof(sum)); memset(mp,0,sizeof(mp)); for(int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); mp[x][y]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j]; } memset(f,0x3f,sizeof(f)); printf("Case %d: %d\n",++kase,dp(1,1,n,m)); } return 0; }
原文：https://www.cnblogs.com/plysc/p/10885043.html
