[luogu] P2979 Cheese Towers S 完全背包dp和状态机

前言

好难一题,没想到都没看懂,呜呜呜 传送门 :

思路

一开始看错了,以为只可以拿一个,就果断 01 01 01背包(竟然过样例了! == WA

本题看上去是一个完全背包问题

对于问题分类

• 要么放大奶酪在上面 (增加奶酪数
• 要么不放在上面 (那么可能放的奶酪少

所以对于第一种我们可以直接使用完全背包计算出来

不过为什么最后他们会得出5/4这个数值,(因为体积变大的上限就是这个?

第二种,我们只需要让每一个奶酪当最上面的那个即可,然后求一次最大值

(当然如果在不知道5/4这个数值的时候,我们也可以使用状态机+完全背包

CODE

const int N = 2e3+10;
int f[N];
int n,t,k;
int a[N],v[N];


void solve()
{
	cin>>n>>t>>k;
	for(int i=1;i>v[i]>>a[i];

//sort(a+1,a+1+n);

	for(int i=1;i