这题其实和普通的DP题没什么区别，只是需要用dp[i]表示i状态下能够达到的最大值，而且由于有负数，需要将坐标轴整体平移一下。
在一进一步说，还是要求出所有的状态，类似穷举了。我想了下，如果真的要优化，可以只将出现过的状态记下来，这样扫描的时候可以剪去一些时间，也许0MS就是这么做的吧^_^ ,复杂度O(10^7)。
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 999999999
int dp[400001];
int n;
int l,r;
#define OFFSET 200000
int main()
{
fill(dp,dp+400001,-INF);
dp[OFFSET]=0;
l=r=OFFSET;
scanf("%d",&n);
int i,j;
int a,b;
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
if(a<=0&&b<=0)
continue;
if(a<0)
{
int k;
for(k=l;k<=r;k++)
{
if(dp[k]!=-INF)
{
if(k+a<l)
l=k+a;
if(dp[k+a]==-INF)
dp[k+a]=dp[k]+b;
else
dp[k+a]=max(dp[k+a],dp[k]+b);
}
}
}
else
{
int k;
for(k=r;k>=l;k--)
{
if(dp[k]!=-INF)
{
if(k+a>r)
r=k+a;
if(dp[k+a]==-INF)
dp[k+a]=dp[k]+b;
else
dp[k+a]=max(dp[k+a],dp[k]+b);
}
}
}
}
int res=0;
int k;
for(k=OFFSET;k<=OFFSET+1000*n;k++)
{
if(dp[k]>0&&k-OFFSET+dp[k]>res)
res=k-OFFSET+dp[k];
}
printf("%d\n",res);
return 0;
}