【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4247
【题目大意】
JOI君有N个装在手机上的挂饰，编号为1...N。 JOI君可以将其中的一些装在手机上。
JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。
每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。
此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。
如果JOI君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。
JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，
而且一个都不挂也是可以的。
【题解】
我们发现每个挂钩相当于代价为1-v，价值为c的物品，
那么当代价小于0时，我们倒着做01背包，否则，正着做01背包，
处理一下下标为负的问题即可。
最后答案为dp[-n……1]的最大值。
【代码】
#include <cstdio>
#include <cstring>
#include <algorithm>
const int M=2020;
using namespace std;
int n;
struct Array{
long long a[M<<1];
long long& operator [] (int x){
return a[min(max(x,-n),n)+2000];
}
}dp;
int main(){
while(~scanf("%d",&n)){
memset(&dp,0xef,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
int v,c;
scanf("%d%d",&v,&c); v=1-v;
if(v>0){for(int j=n;j>=-n;j--)dp[j+v]=max(dp[j+v],dp[j]+c);}
else{for(int j=-n;j<=n;j++)dp[j+v]=max(dp[j+v],dp[j]+c);}
}long long ans=0;
for(int i=-n;i<=1;i++)ans=max(ans,dp[i]);
printf("%lld\n",ans);
}return 0;
}