前言

一道背包 DP 的好题，让我在模拟赛时死在了黄题上。。。

题目大意

题面已经说的很清楚了，没什么好说的了 qwq。

思路分析

定义

dp_{i,j}

为使用前

i

种操作方案，初始有

j

张门票时最多额外获得

dp_{i,j}

块巧克力。

易得转移方程：

dp_{i,j} = \begin{cases} dp_{i-1,j} & j<a_{i} \\ \max(dp_{i-1,j},dp_{i,j-a_{i}+b_{i}}) & j\ge a_{i} \end{cases}

接下来处理拓扑序（即处理操作的顺序，《深进》中有一章用了这样的表达），发现进行

a_{i}

较大的操作后仍可能进行

a_{i}

较小的操作，故按

a_{i}

升序排序。

AC Code

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=505,M=1e5+5;
int n,m,dp[M];
struct node{
	int a,b;
	friend bool operator<(node x,node y){
		return x.a<y.a;
	}
}a[N];
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>a[i].a>>a[i].b;
	sort(a,a+n);
	for(int i=0;i<n;i++)
		for(int j=a[i].a;j<=m;j++)
			dp[j]=max(dp[j],dp[j-a[i].a+a[i].b]+a[i].b);
	for(int i=1,ans=0,s=0;i<=m;i++){
		if(s+ans<i)
			ans++,s=dp[ans];
		cout<<ans<<"\n";
	}
	return 0;
}

题解：P11783 [JOIGST 2024] 交换门票 / Increase Chocolates

文章操作

前言

题目大意

思路分析

AC Code

相关推荐

评论

题解：P11783 [JOIGST 2024] 交换门票 / Increase Chocolates