原题传送门

VJ传送门

题意

给定

n

n

n 个人的 聪明值 Si有趣值 Fi,从中挑任意个数的人,使得聪明值之和和有趣值之和都不为负的前提下,相加最大

1

<

=

n

<

=

100

,

1000

<

=

S

i

,

F

i

<

=

1000

1<=n<=100,-1000<=Si,Fi<=1000

1<=n<=100,1000<=Si,Fi<=1000)

思路

在原来的01背包中,在对体积的限制下,求价值的最大值。在这题中,对两个值都有限制,所以可以固定其中一个值(把它视作01背包中的体积),求另一个值的最大值(价值) , 这样做完背包之后再扫一遍找符合条件下的最大值即可。在这里我们把聪明值当作体积,把有趣值当作价值。
因为值可能是负数,所以还要做个小处理,详见代码。(其实是在补几个月前的题

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110 , M = 1e5 + 5;

int s[N] , f[N] , dp[2 * M] , tot = M , n , ans;
// 因为索引不能是负数,所以在这里1e5+5代表开心值0
int main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> s[i] >> f[i];
        if(s[i] > 0) tot += s[i];
    }

    for(int i = 0 ; i <= tot ; i ++) dp[i] = -1e8;
    dp[M] = 0;
    for(int i = 1 ; i <= n ; i ++){
        if(s[i] > 0){//01背包的一维优化,从右向左更新,用上一层的状态更新当前层
            for(int j = tot ; j >= s[i] ; j --)
                dp[j] = max(dp[j] , dp[j - s[i]] + f[i]);
        }
        else{//s[i] < 0 , 上一层状态的下标大于当前层,所以从左向右
            for(int j = 0 ; j <= tot + s[i] ; j ++)
                dp[j] = max(dp[j] , dp[j - s[i]] + f[i]);
        }
    }

    for(int i = M ; i <= tot ; i ++)
        if(dp[i] >= 0 && i - M + dp[i] > ans) ans = i - M + dp[i];

    cout << ans;

    return 0;
}