自动搬运

查看原文

来自洛谷，原作者为

	81179332_ 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:34:38，当前版本为作者最后更新于2020-06-24 16:00:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $f_{i,j,k,l}$ 表示放了前 $i$ 本书，第一层厚度为 $j$，第二层厚度为 $k$，第三层厚度为 $l$ 的最小高度和

容易想到，我们将所有书按照高度从大到小排序，那么每一层的高度就是第一个放入该层的书的高度

记 $sum_i=\sum\limits_{j=1}^i t_j$显然，$j+k+l=sum_i$，则 $l=sum_i-j-k$，由此，我们可以省掉 $l$ 这一维

再加一个滚动数组优化就可以啦

转移方程较为简单，见代码，采用刷表法比较好写

//timeuse:20min
const int N = 80,M = 2110;
int n;
struct book { int h,t; }a[N];
int f[2][M][M],sum[N];
void minn(int &a,int b) { if(a > b) a = b; }
int main()
{
	freopen("random.in","r",stdin);
	freopen("sol.out","w",stdout);
	n = read();for(int i = 1;i <= n;i++) a[i].h = read(),a[i].t = read();
	sort(a + 1,a + 1 + n,[&](book u,book v) { return u.h > v.h; });
	for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + a[i].t;
	memset(f[0],63,sizeof(f));f[0][0][0] = 0;
	for(int i = 1;i <= n;i++)
	{
		int now = i & 1,pre = now ^ 1;
		memset(f[now],63,sizeof(f[now]));
		for(int j = 0;j <= sum[i - 1];j++) for(int k = 0;k <= sum[i - 1];k++)
		{
			if(j == 0) minn(f[now][j + a[i].t][k],f[pre][j][k] + a[i].h);
			else minn(f[now][j + a[i].t][k],f[pre][j][k]);
			if(k == 0) minn(f[now][j][k + a[i].t],f[pre][j][k] + a[i].h);
			else minn(f[now][j][k + a[i].t],f[pre][j][k]);
			if(sum[i - 1] - j - k == 0) minn(f[now][j][k],f[pre][j][k] + a[i].h);
			else minn(f[now][j][k],f[pre][j][k]);
		}
	}ll ans = LINF;
	for(int i = 1;i <= sum[n];i++) for(int j = 1;j <= sum[n];j++) if(sum[n] - i - j > 0)
		ans = min(ans,(ll)max(max(i,j),sum[n] - i - j) * f[n & 1][i][j]);
	fprint(ans);
	return 0;
}