题目地址:http://poj.org/problem?id=2184

题目大意

给你$N(N \leq 100)$个数$S_1, S_2, \cdots, S_N$和$F_1, F_2, \cdots, F_N$,$(S_i \in [-1000, 1000], F_i \in [-1000, 1000]$,问选其中的$S$的和$TS$与$F$的和$TF$,使$TS, TF \geq 0$且$TS+TF$最大。

思路

以TS和为状态求最大的TF,即$dp[TS] = TF$,由于$TS \in [-100000, 100000]$,则设$dp[TS], TS \in [0, 200000],其中dp[zero=100000]即TS=0$。

首先初始化$dp$为$-INF$,$dp[zero]=0$,然后根据01背包,以$TS$为容量,$TF$为价值进行求解。。

这里写起来好多坑主要就是处理零的状态,初始化的坑,以及当$S_i$为负数时候的处理。。

AC代码

/*************************************************************************
    > File Name: 2184.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-20 二 20:41:56 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int N;
int s[102], f[102];
const int zero = 100000;
const int MAX_S = 200000;
int dp[MAX_S+1]; // 以s和为状态求最大f,即dp[s] = f; s范围[-100000, 100000], 以zero=100000为零点
int max_s; // TS的最大值
int min_s; // TS的最小值

void solve() {
    for(int i=min_s;i<=max_s; ++i) dp[i+zero] = -0x3f3f3f3f; // 从最小到大初始化,注意zero
    dp[zero] = 0; // TS=0时TF=0初始化

    for(int i=0; i<N; ++i) {
        if(s[i] >= 0) // 正数的时候,应该逆序,这样才能保证前面的值没用过,即$dp[j-s[i]]$
            for(int j=max_s; j-s[i]>=min_s; --j) dp[j+zero] = max(dp[j+zero], dp[j+zero-s[i]]+f[i]); 
        else // 负数的时候,应该正序,这样才能保证后面的值都没用过,即$dp[j+s[i]], s[i] = -s[i]$
            for(int j=min_s; j-s[i]<=max_s; ++j) dp[j+zero] = max(dp[j+zero], dp[j+zero-s[i]]+f[i]);
    }

    int ans = 0;

    for(int i=0; i<=max_s; ++i) {
        if(dp[i+zero] >=0)
            ans = max(ans, dp[i+zero] + i);
    }

    cout << ans << endl;
}

int main()
{
#ifdef Oj
    freopen("2184.in", "r", stdin);
#endif
    cin >> N;
    for(int i=0; i<N; ++i) {
        cin >> s[i] >> f[i];
        if(s[i] >= 0) max_s += s[i]; // 计算TS的最大值
        else min_s += s[i]; // 计算TS的最小值
    }
    solve();
    return 0;
}