這題其實和普通的DP題沒什么區(qū)別，只是需要用dp[i]表示i狀態(tài)下能夠達到的最大值，而且由于有負數(shù)，需要將坐標軸整體平移一下。
在一進一步說，還是要求出所有的狀態(tài)，類似窮舉了。我想了下，如果真的要優(yōu)化，可以只將出現(xiàn)過的狀態(tà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;
}