Codeforces 1132E (看题解)

感觉这个题挺有意思的， 我们可以将 L = lcm(1, 2, 3, ... , 8) 看作一组。

然后用dp[ i ][ j ]表示到第 i 种物品当前的值为 j 能用L的最大数量。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long

using namespace std;

const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);

LL W, c[9];
LL dp[10][840 * 8 + 10];

int main() {
    scanf("%lld", &W);
    for(int i = 1; i <= 8; i++) scanf("%lld", &c[i]);
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 0; i <= 7; i++) {
        for(int j = 0; j <= 840 * 8; j++) {
            if(~dp[i][j]) {
                LL up = 840 / (i + 1);
                up = min(up, c[i + 1]);
                for(int k = 0; k <= up; k++) {
                    dp[i + 1][j + k * (i + 1)] = max(dp[i + 1][j + k * (i + 1)], dp[i][j] + (c[i + 1] - k) / (840 / (i + 1)));
                }
            }
        }
    }
    LL ans = 0;
    for(int i = 0; i <= 840 * 8; i++) {
        if(i <= W && ~dp[8][i]) {
            ans = max(ans, i + 840 * (min(dp[8][i], (W - i) / 840)));
        }
    }
    printf("%lld
", ans);
    return 0;
}

/*
*/