swust2793[奇怪的01]

发表于 | 分类于 ， | 阅读数 次

链接:swust2793[奇怪的01]

题解

  • 花费为负数倒着01,然后偏移一下就好 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rint register int 
    #define rep(i,x,y) for(rint i=x;i<=y;++i)
    #define repd(i,x,y) for(rint i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int M=2e5;
    const int N=1e6+7;
    const int inf=0x3f3f3f3f;
    int dp[N],n,V,ans;
    template <typename T>inline void read(T &x){
    	x=0;char c;int sign=1;
    	do{c=getchar(); if(c=='-')sign=-1;}while(c<'0'||c>'9');
    	do{x=x*10+c-'0'; c=getchar();}while(c>='0'&&c<='9');
    	x*=sign;
    }
    int main(){
    	while(~scanf("%d",&n)){
    		rep(i,0,M)dp[i]=-inf;
    		dp[100000]=0;
    		rep(i,1,n){
    			int c,v;
    			read(v);read(c);
    			if(v>0)repd(j,M,v)dp[j]=max(dp[j],dp[j-v]+c);
    			else rep(j,0,M+v-1)dp[j]=max(dp[j],dp[j-v]+c);
    		}
    		rep(i,100000,M)if(dp[i]>0)ans=max(ans,i+dp[i]-100000);
    		printf("%d\n",ans);
    	}
    	return 0;
    }