洛谷 P4095 HEOI2013 Eden 的新背包问题

url: https://www.luogu.com.cn/problem/P4095

tag:
动态规划，背包DP，进制，枚举

思路：
多重背包问题为基础，做两次01背包，前一次后一次，之后对于每次询问的id就跳过那个id求可能的最大值。

代码：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
typedef long long LL;  
const int N = 100010;  
struct node{  
    int id;LL s;  
}w[N], v[N];  
LL f1[N][1010], f2[N][1010];  
int idx, m, n;  
int main()  
{  
    cin >> n;  
    for (int i = 1; i <= n;  i++)  
    {  
        int cw, cv, c;  
        cin >> cw >> cv >> c;  
        int now = 1;  
        while (now <= c)  
        {  
            w[++idx].s = cw * now, v[idx].s = cv * now;  
            w[idx].id = i, v[idx].id = i;  
            c -= now, now *= 2;  
        }  
        if(c) {  
            w[++idx].s = cw * c, v[idx].s = cv * c;  
            w[idx].id = i, v[idx].id = i;  
        }  
    }  
    cin >> m;  
    n = idx;  
    for (int i = 1; i <= n; i ++)  
    {  
        for (int j = 0; j <= 1000; j ++) f1[i][j] = f1[i - 1][j];  
        for (int j = 1000; j >= w[i].s; j --)  
        {  
            f1[i][j] = max(f1[i][j], f1[i - 1][j - w[i].s] + v[i].s);  
        }  
    }  
    for (int i = n; i >= 1; i --)  
    {  
        for (int j = 0; j <= 1000; j ++) f2[i][j] = f2[i + 1][j];  
        for (int j = 1000; j >= w[i].s; j --)  
        {  
            f2[i][j] = max(f2[i][j], f2[i + 1][j - w[i].s] + v[i].s);  
        }  
    }  
    for (int k = 1; k <= m; k ++)  
    {  
        int cn, V;  
        cin >> cn >> V;  
        cn ++;  
        LL ans = 0;  
        int l = 0, r = 0;  
        while (w[l + 1].id < cn && l < n) ++ l;  
        r = l;  
        while (w[r + 1].id <= cn && r < n) ++ r;  
        for (int j = 0; j <= V; j++)  
        {  
            ans = max(ans, f1[l][j] + f2[r + 1][V - j]);  
        }  
        cout << ans << endl;  
    }  
    return 0;  
}