AtCoder Beginner Contest 383

Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）

其实感觉 E 还挺有意思。F 基本想对了，可惜差了一点。这两题过了很多人，还是我太菜了。

F - Diversity

有 $n$ 件商品，第 $i$ 件商品价格为 $P_i$，价值为 $U_i$，颜色为 $C_i$。要求在总金额不超过 $X$ 的条件下最大化满意度，满意度定义为

$$S+T\times K$$

其中 $S$ 为选择商品价值之和，$T$ 为选择商品不同颜色的数量，$K$ 是一个给定的常数。

稍有变化的背包。很自然的想法是按颜色枚举，记 $f_{i,j}$ 为前 $i$ 种颜色，容量为 $j$ 的最大价值，然后倒着枚举容量 dp。关键在于如何区分某种颜色第一次被选取和后续被选取。办法很巧妙，第一次选取从 $f_{i-1}$ 转移，后续选取从 $f_i$ 转移。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=505;
vector<pii> v[505];
ll f[N][50005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,x,y;cin>>n>>x>>y;
    for(int i=1;i<=n;i++)
    {
        int p,u,c;cin>>p>>u>>c;
        v[c].push_back({p,u});
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=x;j++) f[i][j]=-1e18;
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(auto k:v[i])
            for(int j=x;j>=k.first;j--)
            {
                f[i][j]=max(f[i][j],f[i-1][j-k.first]+k.second+y);
                f[i][j]=max(f[i][j],f[i][j-k.first]+k.second);
            }
        for(int j=x;j>=0;j--) f[i][j]=max(f[i][j],f[i-1][j]);
    }
    cout<<*max_element(f[n],f[n]+x+1)<<'\n';
    return 0;
}