UESTC 1218 Pick The Sticks （dp )

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=4e3+10;
typedef long long LL;
LL dp[N][5]; // 0,1,2分别表示露在外面的木棍数量
LL a[1010],v[1010];
int main()
{
//freopen("cin.txt","r",stdin);
LL n,t=0,m,len;
cin>>n;
while(n--){
scanf("%lld%lld",&m,&len);
len=len*2;
LL ans=0;
for(int i=0;i<m;i++){
scanf("%lld%lld",&a[i],&v[i]);
a[i]=a[i]*2;
ans=max(ans,v[i]);
}
memset(dp,0,sizeof(dp));
for(int i=0;i<m;i++){
for(int j=len;j>=a[i]/2;j--){
dp[j][1]=max(dp[j-a[i]/2][0]+v[i],dp[j][1]); // outside
dp[j][2]=max(dp[j-a[i]/2][1]+v[i],dp[j][2]);
// 不放就仍然使用原值
if(j>=a[i]){
dp[j][0]=max(dp[j-a[i]][0]+v[i],dp[j][0]); //inside
dp[j][1]=max(dp[j-a[i]][1]+v[i],dp[j][1]);
dp[j][2]=max(dp[j-a[i]][2]+v[i],dp[j][2]);
}
}
}
for(int i=0;i<3;i++){
ans=max(ans,dp[len][i]);
}
printf("Case #%lld: %lld\n",++t,ans);
}
return 0;
}