【codeforces 808E】【Selling Souvenirs】【貪心】【動态規劃】

題目大意

很多個物體01背包，size小于等于3，求給定容量最大價值。

解題思路

考慮隻有1和2的情況，先排一波序，設f[i]表示用了i容量的最大價值，順便存一下目前用了多少個2，可以發現貪心地取是正确的，方案唯一，因為我們已經排過序了。考慮3的情況，排序後一樣枚舉選多少個3，剩下的用1和2湊即可。

code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j,k) for(int i=begin[j][k];i;i=next[j][i])
using namespace std;
int const mn=e5+,mm=*1e5+,inf=e9+;
int n,m,f[mm];
LL g[mm];
struct rec{
    int w,c;
};
rec a[mn];
bool cmp(rec x,rec y){
    return (x.w<y.w)||((x.w==y.w)&&(x.c>y.c));
}
int main(){
    //freopen("d.in","r",stdin);
    //freopen("d.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,,n)scanf("%d%d",&a[i].w,&a[i].c);
    sort(a+,a+n+,cmp);
    int tmp;
    fo(i,,n+)if(a[i].w!=){tmp=i;break;}
    int tm2=tmp;
    fo(i,tmp,n+)if(a[i].w!=){tm2=i;break;}
    f[]=;if(tmp!=)g[]=a[].c;
    fo(i,,m){
    if((i-f[i-]*2>=tmp)&&(tmp+f[i-]>=tm2))f[i]=f[i-],g[i]=g[i-];
    else if((tmp+f[i-]>=tm2)||((i-f[i-]*2<tmp)&&
    (g[i-]+a[i-f[i-]*2].c>g[i-]+a[tmp+f[i-]].c)))f[i]=f[i-],g[i]=g[i-]+a[i-f[i-]*2].c;
    else f[i]=f[i-]+,g[i]=g[i-]+a[tmp+f[i-]].c;
    if(g[i-]>g[i])f[i]=f[i-],g[i]=g[i-];
    }
    LL ans=g[m],tm3=,tm4=m;
    fo(i,tm2,n){
        tm4-=;tm3+=a[i].c;
        if(tm4<)break;
        ans=max(ans,g[tm4]+tm3);
    }
    printf("%I64d",ans);
    return ;
}