【0909 B组】切蛋糕 题解

原题链接：切蛋糕。

题意

给定一个 \(n\) 行 \(m\) 列的蛋糕，问横着切 \(i\) 刀，竖着切 \(j\) 刀后美味度最小的蛋糕的美味度尽可能大。一块蛋糕的美味度为它所含有的小块的美味度之和。

数据范围：\(1 \le n,m \le 14\)。

思路

看到数据范围，我们可以考虑一种类似于状态压缩的思想，先枚举每一行切的位置的所有情况。对于每一种情况设 \(dp_{i,j}\) 表示枚举到第 \(i\) 列，在列上一共切了 \(j\) 刀时美味度可以达到的最大值。那么可以先预处理处 \(num_{s,L,R}\) 表示在行的状态为 \(s\) 的情况下，在 \(L\) 列和 \(R\) 列分别切一刀时的美味度的最小值。那么则可以推出状态转移方程为：\(dp_{i,j}= \max(dp_{i,j},dp_{k-1,j-1}+num_{i,k})\)。枚举行的情况复杂度 \(O(2^{n})\)，预处理和 \(dp\) 转移均为 \(O(n^{3})\)，总时间复杂度 \(O(2^{n}n^{3})\)，可以通过。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define inf_db
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 15;
int n,m,a[MAXN][MAXN],sum[MAXN][MAXN],dp[MAXN][MAXN],ans[MAXN][MAXN],lastp,lastq;
int dis[MAXN][MAXN][MAXN][MAXN],num[MAXN][MAXN];
inline int calc(int x,int y,int p,int q){return sum[x][y] + sum[p - 1][q - 1] - sum[p - 1][y] - sum[x][q - 1];}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(re int i = 1;i <= n;i++)
		for(re int j = 1;j <= m;j++)
		{
			scanf("%lld",&a[i][j]);
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
		}
	for(re int i = 1;i <= n;i++) for(re int j = 1;j <= m;j++)
	for(re int p = 1;p <= i;p++) for(re int q = 1;q <= j;q++) dis[i][j][p][q] = calc(i,j,p,q);
	for(re int i = 0;i < (1 << (n - 1));i++)
	{
		for(re int L = 1;L <= m;L++)
			for(re int R = L;R <= m;R++)
			{
				int lastj = 1;num[L][R] = 1e9;
				for(re int j = 1;j <= n;j++)
				{
					if(!(i & (1 << (j - 1))) && (j != n)) continue;
					num[L][R] = min(num[L][R],dis[j][R][lastj][L]);
					lastj = j + 1;
				}
			}
		for(re int j = 0;j <= m;j++) for(re int k = 0;k <= m;k++) dp[j][k] = -1e9;
		dp[0][0] = 1e9;
		for(re int j = 1;j <= m;j++) for(re int k = 1;k <= j;k++)
		for(re int p = 1;p <= j;p++) dp[j][p] = max(dp[j][p],min(dp[k - 1][p - 1],num[k][j]));
		int id = __builtin_popcount(i) + 1;
		for(re int k = 1;k <= m;k++) ans[id][k] = max(ans[id][k],dp[m][k]);
	} 
	for(re int i = 1;i <= n;i++) 
	{
		for(re int j = 1;j <= m;j++) printf("%lld ",ans[i][j]);
		puts("");
	}	
	return 0;
}