本文迁移自洛谷原文。
首先，我们可以先选择题目，再把剩下不要的让家长拿走。这一定是最优的。
然后就是个基础的背包。dp[i][j]表示考虑带第i个题目时，花费了j个时间的最大毒瘤值。
为了最后的计算，还要记录一下路径。
最后通过记录的路径求出选了那些题目，然后贪心的从大到小排序，选前k个*2即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #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';
}
|