CF1974E Money Buys Happiness

题目传送门

大致思路

注意到题目限制条件快乐值总和$≤10^{5}$
又 $(1≤m≤50)$,可以想到 $dp$:

记$dp_{i,j}$为在第 $i$ 天获得 $j$ 快乐值的最小花费,于是有:
$dp_{i,j}=min(dp_{i-1,j},dp_{i,{j-h_i}}+c_i)$
对于第二项,当且仅当 $h_i≤j$ 且 $c_i+dp_{i,{j-h_i}}≤cur$ 时可以取到
特别地,当 $j==h_i$ 时额外判断一下 $dp_{i,h_i}=min(c_i,dp_{i,h_i})$

然后就是细节:花费可能会超出 $int$ ,要用 $long\ long$
初始化所有的dp项为极大数字. 特别地: $dp_{i,0}=0$

Code

void solve() {
    int m,x;
    cin >> m >> x;
    int sum=0;
    vector<array<int,2>> hp(m+1);
    int cur=-x;
    for (int i=1;i<=m;i++) {
        cin >> hp[i][0] >>hp[i][1];
        sum+=hp[i][1];
    }
    const int M=1e12;
    vector<vector<int>> dp(m+1,vector<int>(sum+1,M));
    for (int i=1;i<=m;i++) {
        dp[i][0]=0;
        cur+=x;
        int add=hp[i][1];
        for (int h=sum;h>=0;h--) {
            dp[i][h]=min(dp[i-1][h],dp[i][h]);
            if (h-add>=0 && cur-dp[i-1][h-add]>=hp[i][0]) dp[i][h]=min(dp[i][h],dp[i-1][h-add]+hp[i][0]);
        }
        if (cur>=hp[i][0]) dp[i][add]=min(dp[i][add],hp[i][0]);
    }
    int ans=0;
    for (int h=0;h<=sum;h++) if (dp[m][h]!=M) ans=h;
    cout << ans <<el;
}