题解：AT_abc415_g [ABC415G] Get Many Cola

· · 题解

思路

看到此题考虑用背包 dp，枚举 1 \le i \le n 和 1 \le j \le m 把 a_j-b_j 当重量，a_j 当价值，但是枚举 i 就已经超时了，我们根据 D 题的解题思路也就是贪心，结合 dp 想到在 n 较大的时候用贪心先把 n 降下来再用 dp 具体看代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5;
int n,m,c[305],dp[N+5],x,y,ans; 
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        c[x]=max(c[x],y);//花费同样的瓶子，得到的可乐不一定一样，此时取最大 
    }
    for(int i=1;i<=300;i++)//直接dp会超时，考虑大贪心，小dp 
        for(int j=i;j<=N;j++)//确保有i个瓶子兑换 
            dp[j]=max(dp[j],dp[j-(i-c[i])]+i);
    if(n<N){//n太小以致于可以直接dp 
        cout<<dp[n];
        return 0;
    }
    for(int i=1;i<=300;i++){//大贪心,枚举每种兑换方案 
        int cs=(n-N+i)/(i-c[i]);//+i是为了防止下面n-cs*(i-c[i])超过N，因为我们dp只到了N 
        ans=max(ans,cs*i+dp[n-cs*(i-c[i])]);//cs*i是直接用i换c[i]的收益，dp[...]是dp的收益，然后对于每个兑换方案取最大值 
    }
    cout<<ans;
    return 0;
}