题目
有(n)个物品,对于第(i)个物品,
有两种属性,第一种属性为(x_i),第二种属性为(y_i)
问选择若干个物品使得(sum{x_j}geq 0)且(sum{y_j}geq 0)的情况下,
(sum{x_j+y_j})最大,(nleq 400)
分析
设(dp[x])表示选择第一种属性和为(x)时能取得的最大的(y),
直接平移下标跑01背包即可,最后求最大值
代码
#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
int f[800011],n,ans;
inline signed iut(){
rr int ans=0,f=1; rr char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans*f;
}
inline void Max(int &a,int b){a=a>b?a:b;}
signed main(){
memset(f,0xcf,sizeof(f)),
n=iut(),f[n*1000]=0;
for (rr int i=1;i<=n;++i){
rr int w=iut(),c=iut();
if (w<0)
for (rr int j=-w;j<=n*2000;++j)
Max(f[j+w],f[j]+c);
else for (rr int j=n*2000;j>=w;--j)
Max(f[j],f[j-w]+c);
}
for (rr int i=n*1000;i<=n*2000;++i)
if (f[i]>=0) Max(ans,i-n*1000+f[i]);
return !printf("%d",ans);
}