【dp】E. Selling Souvenirs

http://codeforces.com/contest/808/problem/E

题意：给定n个重量为可能1,2,3的纪念品和各自的价值，问在背包总重量不超过m的条件下总价值最大为多少。

其中1 ≤ n ≤ 100000, 1 ≤ m ≤ 300000

首先可以想到的是重量相同的情况下，优先选择价值大的纪念品。所以我们可以把价值为1,2,3的纪念品分开，分别排序。

我们可以枚举重量为3的纪念品的个数为x，然后剩下的重量m-sum{3-elements}由1和2混合得出，这里可以动态规划预处理。

dp[i]是一个三元组{cost,cnt1,cnt2}，分别表示重量为i的情况下的最大价值，以及这时候1和2分别用了多少。

dp[i]可以dp[i-1]和dp[i-2]推出。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<set>
  8 #include<map> 
  9 #include<utility> 
 10 using namespace std;
 11 typedef long long ll;
 12 const int maxn=3e5+2;
 13 
 14 struct node
 15 {
 16     ll cost;
 17     int cnt1;
 18     int cnt2;
 19 }dp[maxn];
 20 ll sum[maxn];
 21 ll a[maxn],b[maxn],c[maxn];
 22 int n,m;
 23 int main()
 24 {
 25     scanf("%d%d",&n,&m);
 26     int weight;
 27     ll cost;
 28     int p=0,q=0,r=0;
 29     for(int i=0;i<n;i++)
 30     {
 31     //    scanf("%d%lld",&weight,&cost);
 32         cin>>weight>>cost; 
 33         if(weight==1)
 34         {
 35             a[p++]=cost;
 36         }
 37         else if(weight==2)
 38         {
 39             b[q++]=cost;
 40         }
 41         else
 42         {
 43             c[r++]=cost;
 44         }
 45     }
 46     sort(a,a+p);
 47     sort(b,b+q);
 48     sort(c,c+r);
 49     dp[0].cost=0;
 50     dp[0].cnt1=p;
 51     dp[0].cnt2=q;
 52     dp[1].cost=a[p-1];
 53     dp[1].cnt1=p-1;
 54     dp[1].cnt2=q;
 55     for(int i=2;i<=m;i++)
 56     {
 57         if(dp[i-1].cnt1-1>=0&&dp[i-2].cnt2-1>=0)
 58         {
 59             if(dp[i-1].cost+a[dp[i-1].cnt1-1]>dp[i-2].cost+b[dp[i-2].cnt2-1])
 60             {
 61                 dp[i].cost=dp[i-1].cost+a[dp[i-1].cnt1-1];
 62                 dp[i].cnt1=dp[i-1].cnt1-1;
 63                 dp[i].cnt2=dp[i-1].cnt2;
 64             }
 65             else
 66             {
 67                 dp[i].cost=dp[i-2].cost+b[dp[i-2].cnt2-1];
 68                 dp[i].cnt1=dp[i-2].cnt1;
 69                 dp[i].cnt2=dp[i-2].cnt2-1;
 70             }
 71         }
 72         else if(dp[i-1].cnt1-1<0&&dp[i-2].cnt2-1>=0)
 73         {
 74             dp[i].cost=dp[i-2].cost+b[dp[i-2].cnt2-1];
 75                 dp[i].cnt1=dp[i-2].cnt1;
 76                 dp[i].cnt2=dp[i-2].cnt2-1;
 77         }
 78         else if(dp[i-1].cnt1-1>=0&&dp[i-2].cnt2-1<0)
 79         {
 80             dp[i].cost=dp[i-1].cost+a[dp[i-1].cnt1-1];
 81                 dp[i].cnt1=dp[i-1].cnt1-1;
 82                 dp[i].cnt2=dp[i-1].cnt2;
 83         }
 84         else
 85         {
 86             break;
 87         }
 88     }
 89     sum[r]=0;
 90     for(int i=r-1;i>=0;i--)
 91     {
 92         sum[i]=sum[i+1]+c[i];
 93     }
 94     ll ans=0;
 95     for(int i=0;i<=m;i++)
 96     {
 97         int x=(m-i)/3;
 98         ll temp=dp[i].cost+sum[max(r-x,0)];
 99         if(temp>ans)
100         {
101             ans=temp;
102         }
103     }
104     cout<<ans<<endl; 
105     
106     
107     return 0;
108 }

View Code

注意一些小细节：

1 ll temp=dp[i].cost+sum[max(r-x,0)];

重量为3的可能不够用