問題概要

$N$ 個の開発案がある。これらの開発案によって上昇し得るパラメータが $K$ 種類ある。

開発案 $i$ ( $i = 1, 2, \dots, N$ ) を採用すると、パラメータ $k$ ( $k = 1, 2, \dots, K$ ) の値が $A_{i, k}$ だけ上昇する。その分、 $C_{i}$ のコストがかかる。

すべてのパラメータを $P$ 以上とするために必要な最小コストを求めよ。不可能な場合は -1 を出力せよ。

制約

$1 \le N \le 100$
$1 \le K, P \le 5$

考えたこと

パラメータ状態として、あり得る場合の数を見積もる。

$P$ 以上になる部分はすべて $P$ としてよい (カンストしたとみなす) ので、場合の数は $(P+1)^{K}$ 通りとなる。これは十分小さいので次のような DP が組める。

dp[i][{v[0], v[1], ..., v[K-1]}] ← 最初の $i$ 個の開発案のみからいくつか採用したときの、各パラメータ値が v[0], v[1], ..., v[K-1] となる状態にするのに必要な最小コスト

計算量は $O(N K P^{K})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    // 入力
    long long N, K, P;
    cin >> N >> K >> P;
    vector<long long> C(N);
    vector<vector<long long>> A(N, vector<long long>(K));
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
        for (int j = 0; j < K; ++j) cin >> A[i][j];
    }
    
    // DP
    map<vector<int>, long long> dp;
    dp[vector<int>(K, 0)] = 0;
    for (int i = 0; i < N; ++i) {
        map<vector<int>, long long> dp2;
        
        // dp2[v] を c と比較して c が小さい場合はそれに update する関数
        auto update = [&](const vector<int> &v, long long c) -> void {
            if (!dp2.count(v)) dp2[v] = c;
            else chmin(dp2[v], c);
        };
        
        for (auto [vec, cost] : dp) {
            update(vec, cost);
            
            vector<int> vec2 = vec;
            for (int j = 0; j < K; ++j) vec2[j] = min(vec[j] + A[i][j], P);
            update(vec2, cost + C[i]);
        }
        swap(dp, dp2);
    }
    
    // 出力
    vector<int> full(K, P);
    cout << (dp.count(full) ? dp[full] : -1) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 322 E - Product Development (緑色, 475 点)

問題概要

制約

考えたこと

コード