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

钓鱼王子 · 2020-04-22 15:48:10 · 题解

一道背包 DP。

设 f_{x,i,j} 表示前 x 道题，花费 i 的时间，使用 j 次翻倍的最大价值。可以类似背包转移，同时也可以用滚动数组。

记得特判 j=0 的情况。

然后，如果选择了全部，就要删去价值最小的（不能选全部）。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
#define re register
using namespace std;
const int Mxdt=5000;    //单次大小
inline char gc() {
    static char buf[Mxdt],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read() {
    re int t=0;
    re char v=gc();
    while(v<'0')v=gc();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
    return t;
}
int n,m,f[1002][1002],a[1002],b[1002],k,sum,mn;
int main() {
    n=read();m=read();k=read();mn=1e9;
    for(re int i=1;i<=n;++i)a[i]=read(),b[i]=read(),sum+=b[i],mn=min(mn,a[i]);
    for(re int i=1;i<=n;++i){
        for(re int j=m;j>=b[i];--j){
            for(re int l=0;l<=k;++l){
                f[j][l]=max(f[j][l],f[j-b[i]][l]+a[i]);
                if(l)f[j][l]=max(f[j][l],f[j-b[i]][l-1]+a[i]*2);
            }
        }
    }
    if(sum<=m)f[m][k]-=mn;
    printf("%d",f[m][k]);
}