Eat Breads

2 secs 1024 MB

dyktr_06

問題

提出

テストケース

解説

$dp[i] :$ 食べたパンの集合が $i$ のときの幸福度の最大値
という動的計画法を考えることによってこの問題に正解することができます。

以下の実装では、 $O(N^2 ・ 2^N)$ ですが、減少分を前計算しておくことによって $O(N ・ 2^N)$ で解くこともできます。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

const long long INF = 0x1fffffffffffffff;

int main(){
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<vector<long long>> b(n, vector<long long>(n - 1));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n - 1; j++){
            cin >> b[i][j];
        }
    }

    vector<long long> dp(1 << n, -INF);
    dp[0] = 0;
    for(int i = 0; i < (1 << n); i++){
        if(dp[i] == -INF) continue;
        for(int j = 0; j < n; j++){
            if(!((i >> j) & 1)){
                int bit = i | (1 << j);
                int t = __builtin_popcount(i);
                long long v = a[j];
                for(int k = 0; k < t; k++){
                    v -= b[j][k];
                }
                dp[bit] = max({dp[bit], dp[i], dp[i] + v});
            }
        }
    }

    long long ans = 0;
    for(int i = 0; i < (1 << n); i++){
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}