Yukicoder010 ＋か×か

問題概要

左結合の式の数値$a[i]$のみが$N$個与えられる。”+“か”*“をいれて、$Total$となるようにしたとき、辞書順最小の選択をもとめよ。

$N\leqq50$、$a[i]\leqq10$、$Total\leqq10^5$

yukicoder010

解法

最小の情報を持たせるためにこれを$2$進数表現で保持する。(後で復元できるように)

$dp[i][j]:= a[i]$を使って、演算の選択をしたときに結果が$j$となるような辞書順最小の演算結果 として$DP$を行う。

計算量:$O(N*Tolal)$

別解として半分前列挙(片側探索?)、再帰もある。どちらも指数時間解法。

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VL = vector<LL>;        using VVL = vector<VL>;
    
    
    #define FOR(i, s, e) for (LL(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e18;
    
    
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        LL total; cin >> total;
        VL a(N);
        FOR(i, 0, N) {
            cin >> a[i];
        }
        VVL dp(N, VL(total + 1, LINF));
        dp[0][a[0]] = 0;
        FOR(i, 1, N) {
            FOR(j, 0, total + 1) {
                if (dp[i-1][j] == LINF)continue;
                if(j+a[i] <=total)dp[i][j+a[i]] = min(dp[i][j+a[i]], dp[i-1][j] * 2);     // +
                if(j*a[i]<=total)dp[i][j*a[i]] = min(dp[i][j*a[i]], dp[i-1][j] * 2 + 1); // *
            }
        }
        // 復元 
    
        ans = dp[N-1][total];
        // N-1回
        FOR(i, 0, N - 1) {
            if (ans & (1LL << (N - i - 2))) {
                cout << "*";
            }
            else {
                cout << "+";
            }
        }cout << endl;
    
        return 0;
    }