Educational Codeforces Round 61 (Rated for Div. 2) E. Knapsack

非常经典的dp题，因为1至8的最大公约数是840，任何一个数的和中840的倍数都是可以放在一起算的，

所以我只需要统计840*8的值(每个数字(1-8)的sum%840的总和)，剩下都是840的倍数

dp[i][j] 代表讨论了第i位并且每个数字取余为j的情况

#include <assert.h>

#include <algorithm>

#include <bitset>

#include <climits>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <functional>

#include <iomanip>

#include <iostream>

#include <list>

#include <map>

#include <queue>

#include <set>

#include <stack>

#include <vector>

#include <ctime>

#include <time.h>

using namespace std;

const int N = 2e5 + 5;

const int INF = 0x3f3f3f3f;

typedef long long ll;

ll a[10];

ll dp[10][8400];

int main() {

    ll w;

    while(~scanf("%lld", &w)) {

        for(int i = 0; i < 8; ++i) {

            scanf("%lld", &a[i]);

        }

        memset(dp, -1, sizeof(dp));

        dp[0][0] = 0;

        for(int i = 0; i < 8; ++i) {

            for(int j = 0; j < 8400; ++j) {

                if(dp[i][j] == -1) continue;

                int edge = min(1ll * 840 / (i + 1), a[i]);

                for(int k = 0; k <= edge; ++k) {

                    dp[i + 1][j + k * (i + 1)] = max( dp[i + 1][j + k * (i + 1)], dp[i][j] + (a[i] - k) / (840 / (i + 1)));

                }

            }

        }

        ll ans = -1;

        for(int i = 0; i < 8400; ++i) {

            if(dp[8][i] == -1 || i > w) continue;

            ans = max(ans, i + min( (w - i) / 840, dp[8][i]) * 840);

        }

        printf("%lld\n", ans);

    }

    return 0;

}

巴特西

Educational Codeforces Round 61 (Rated for Div. 2) E. Knapsack

最新文章

热门文章