翻译：有一个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
      
       #define inf 0x3f3f3f3fusing 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