题解 P6433 【「EZEC-1」出题】

· · 题解

首先，我们可以先选择题目，再把剩下不要的让家长拿走。这一定是最优的。

然后就是个基础的背包。dp[i][j]表示考虑带第i个题目时，花费了j个时间的最大毒瘤值。 为了最后的计算，还要记录一下路径。

最后通过记录的路径求出选了那些题目，然后贪心的从大到小排序，选前k个*2即可。

#include<bits/stdc++.h>
using namespace std;
int dp[101][1001],par[101][1001],k;
int a[101],b[101],n,m;
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)cin>>a[i]>>b[i];
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j){
            dp[i][j]=dp[i-1][j],par[i][j]=j;
            if(j>=b[i]){
                if(dp[i][j]<dp[i-1][j-b[i]]+a[i]){
                    dp[i][j]=dp[i-1][j-b[i]]+a[i];
                    par[i][j]=j-b[i];  //记录路径
                }
            }
        }
    }
    vector<int>v;v.clear();
    int mx=-1,wz,ans=0;
    for(int i=0;i<=m;++i){
        if(dp[n][i]>mx){
            mx=dp[n][i];
            wz=i;
        }
    }
    for(int i=n;i;--i){
        int T=par[i][wz];
        if(T==wz);
        else{
            v.push_back(a[i]);
            wz=T;
        }
    }
    sort(v.rbegin(),v.rend());
    if(!v.size()){  //一个特判
        cout<<0<<'\n';
        return 0;
    }
    if(v.size()==n)v.pop_back();
    for(int i=0;i<v.size();++i){
        if(i<k)ans+=v[i]*2;
        else ans+=v[i];
    }
    cout<<ans<<'\n';
}