背包变形。与普通的背包问题不同的是：允许有两个物品可以花费减半。
因此加一维即可，dp[i][j][k]表示前i个物品，有j个花费减半了，总花费为k的情况下的最优解。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } int T,n,L; LL f[2][3][4010]; struct X{int a;LL v;}s[1010]; int main() { scanf("%d",&T); int cas=1; while(T--) { scanf("%d%d",&n,&L); L=L*2; LL ans=0; for(int i=1;i<=n;i++) { scanf("%d%lld",&s[i].a,&s[i].v); s[i].a=s[i].a*2; ans=max(ans,s[i].v); } memset(f,0,sizeof f); int p=1; for(int i=1;i<=n;i++) { p=p^1; for(int j=0;j<=2;j++) { for(int c=0;c<=L;c++) { f[p][j][c]=f[p^1][j][c]; if(c-s[i].a>=0) f[p][j][c]=max(f[p][j][c],f[p^1][j][c-s[i].a]+s[i].v); if(j-1>=0&&c-s[i].a/2>=0) f[p][j][c]=max(f[p][j][c],f[p^1][j-1][c-s[i].a/2]+s[i].v); ans=max(ans,f[p][j][c]); } } } printf("Case #%d: %lld ",cas++,ans); } return 0; }