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

· · 题解

题目传送门

前言

一道背包 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

#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;
}