POJ 2184 DP

思路：

f[j]表示当ts的和为j的时候tf的最大值。

这时候要分情况讨论：

（我把状态平移了101000）

若ts[i]>=0倒序循环

否则正序 （防止ts被用了多次）

f[101000]=0;

for(int i=1;i<=n;i++)

    if(ts[i]>=0)

        for(int j=202000-ts[i];j>=0;j--)

            f[j+ts[i]]=max(f[j+ts[i]],f[j]+tf[i]);

    else

        for(int j=-ts[i];j<=202000;j++)

            f[j+ts[i]]=max(f[j+ts[i]],f[j]+tf[i]);

// by SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,ts[105],tf[105],f[202005],ans=0;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d%d",&ts[i],&tf[i]);

    memset(f,0xcf,sizeof(f));

    f[101000]=0;

    for(int i=1;i<=n;i++)

        if(ts[i]>=0)

            for(int j=202000-ts[i];j>=0;j--)

                f[j+ts[i]]=max(f[j+ts[i]],f[j]+tf[i]);

        else

            for(int j=-ts[i];j<=202000;j++)

                f[j+ts[i]]=max(f[j+ts[i]],f[j]+tf[i]);

    for(int i=101000;i<=202000;i++)

        if(f[i]>=0)ans=max(ans,f[i]+i-101000);

    printf("%d\n",ans);

}