P1089 （C++代码）

解题思路:





注意事项:





参考代码:

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<iostream>  
#include<cmath>  
#include<algorithm>  
#define MAXN 200002  
using namespace std;  
int n,f[102][MAXN],ans=-1;  
struct wu{int x,y;} a[102];   
void init()  
{  
    scanf("%d",&n);  
    int i;  
    for(i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);  
}  
void dp()  
{  
    int i,j;  
    memset(f,-127,sizeof(f));  
    f[0][100000]=0;  
    for(i=1;i<=n;i++)  
    for(j=200000;j>=0;j--)  
        f[i][j]=max(f[i-1][j],f[i-1][j-a[i].x]+a[i].y);  
    for(j=100000;j<=200000;j++)  
       {if(f[n][j]>=0) ans=max(ans,f[n][j]+j-100000);}  
    printf("%d\n",ans);  
}  
int main()  
{  
    init(); dp();  
    return 0;  
}