题目链接

Cow Exhibition POJ - 2184

思路

$$ \begin{aligned}转化成01背包问题，一个量当重量，一个量当价值。\end{aligned} $$

时间复杂度

$$ O(NM) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 2e5 + 100;
const int INF = 0x3f3f3f3f;

int dp[2][MAXN];


int main() {
    int n;
    scanf("%d", &n);// don't forget &
    int dx = 100005;
    for (int i = -100000; i <= 100000; i++) {
        dp[0][dx + i] = dp[1][dx + i] = -INF;
    }
    dp[0][dx + 0] = 0;
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);// don't forget &
        for (int j = -100000; j <= 100000; j++) {
            dp[i & 1][dx + j] = dp[(i - 1) & 1][dx + j];
            int w = j - x;
            if (-100000 <= w && w <= 100000) {
                dp[i & 1][dx + j] = max(dp[i & 1][dx + j], dp[(i - 1) & 1][dx + j - x] + y);
            }
        }
    }
    int ans = -INF;
    for (int i = 0; i <= 100000; i++) {
        if (dp[n & 1][dx + i] >= 0) {
            ans = max(ans, i + dp[n & 1][dx + i]);
        }
    }
    printf("%d", ans);
    return 0;
}