Yukicoder027 板の準備

問題概要

異なる3種類の長さ$A$、$B$、$C$の板を無数に用意できる。 $A$、$B$、$C$は整数の値で自由に決めて良い。 板と板はつなげて伸ばすことができる。 指定された$V_0$、$V_1$、$V_2$、$V_3$の長さの板を作りたい。 最低何枚の板が必要か？

$1\leqq V_i\leqq30$

yukicoder027

解法

$dp(i) :=$ 三種類の板を使用して$i$の長さの板を作るために必要な最小枚数　とする。 一様にやるDPでこれは更新できて、あとは三種類の板の長さをを全探索しながらDPすれば良い。

計算量:$O(max(V_i)^4)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e16;
    
    LL N;
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        VI v(4);
        FOR(i, 0, 4) {
            cin >> v[i];
        }
        int ans = INF;
        FOR(a, 1, 31) {
            FOR(b, a, 31) {
                FOR(c, b, 31) {
                    VI dp(70, INF);
                    dp[0] = 0;
                    FOR(i, 0, 30) {
                        dp[i + a] = min(dp[i + a], dp[i] + 1);
                        dp[i + b] = min(dp[i + b], dp[i] + 1);
                        dp[i + c] = min(dp[i + c], dp[i] + 1);
                    }
                    int f = 1;
                    int ret = 0;
                    FOR(i, 0, 4) {
                        if (dp[v[i]] != INF && dp[v[i]]) {
                            ret += dp[v[i]];
                        }
                        else f = 0;
                    }
                    if (f) {
                        ans = min(ans, ret);
                    }
                }
            }
        }
        cout << ans << "\n";
    
        return 0;
    }