P2340 [USACO03FALL] Cow Exhibition G

题目

P2340 [USACO03FALL] Cow Exhibition G

算法标签: 动态规划, 前缀和, 贪心, 背包问题

思路

因为涉及到对某个奶牛选择或者不选择, 因此和背包问题很像, 求的是智商 + 情商的最大值, 可以定义状态$f[i][j]$, 考虑前$i$只奶牛, 并且总的智商是$j$的情商的最大值, 答案就是枚举每个位置计算智商 + 情商的最大值, 但是奶牛的数量是$400$, 需要的空间是$400\times 1000\times 400\times 4byte$大约是$610MB$, 会爆空间, 需要进行优化, 观察状态转移, 如果选择当前奶牛$f[i-1][j-v_i]+w_i$, 如果不选择当前奶牛$f[i-1][j]$, 可以使用滚动数组进行优化, 本题如果直接优化掉一维空间是错误的, 因为无法判断$v_i$的正负

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 410;
const int offset = 400000;
const int M = 2 * offset + 10;
const int inf = 0x3f3f3f3f;

int n, v[N], w[N];
int f[2][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];

    memset(f, -0x3f, sizeof f);
    f[0][offset] = 0;

    for (int i = 1; i <= n; ++i) {
   
        memset(f[i & 1], -0x3f, sizeof f[i & 1]);
        for (int j = 0; j < M; ++j) {
   
            f[i & 1][j] = f[i - 1 & 1][j];
            if (j - v[i] >= 0 && j - v[i] < M) {
   
                f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - v[i]] + w[i]);
            }
        }
    }

    int ans = 0;
    for (int j = offset; j < M; ++j) {
   
        if (f[n & 1][j] >= 0) ans = max(ans, (j - offset) + f[n & 1][j]);
    }

    cout << ans << "\n";
    return 0;
}