学步园

思路：0/1背包的变形 把s[]当成背包中的费用，f[]当成价值求解，这题的范围是从-1000 
到1000 但数组的下标没有负的 所以加上1000  ，还0/1背包中最重要的一点是
每件物品只能放一次，而保证这的是它循环的顺序 是从V--->cost 
但这是有负值 那就得由cost ---> V 为什么呢，你仔细想想，dp[i][v]
是由dp[i-1][V-cost] 推知的，V-cost ，cost是负的
负负得正，如果还是原来的顺序，那就变成dp[i][v]由dp[i][v-cost]推知了，这就变成了完全背包了。

//948K   
157MS
#include <stdio.h>
#define M 200000
#define N 105
const int inf = -0x3f3f3f3f;
int dp[M+5];
int s[N],f[N];

int max (int a,int b)
{
    return a
> b ? a : b;
}
int main ()
{
    int
n,i,j;
    while
(~scanf ("%d",&n))
    {
       
for (i = 0; i < n; i ++)
           
scanf ("%d%d",&s[i],&f[i]);
       
for (i = 0; i < M+1; i ++)
           
dp[i] = inf;
       
dp[M/2] = 0;
       
for (i = 0; i < n; i ++)
       
{
           
if (s[i] >
0)          
//大于0 由大到小
           
{
               
for (j = M; j >= s[i]; j --)
                   
if (dp[j - s[i]] >
inf)         
//优化
                       
dp[j] = max (dp[j],dp[j - s[i]] + f[i]);
           
}
           
else               
//小于0 由小到大
           
{
               
for (j = 0; j <= M + s[i]; j ++)