D - Flip and Adjust

atcoder.jp

表か裏かで遷移する動的計画法。 dp[i][j] := カードi,...,iまでの和をjにできるなら1、そうでないなら0

dp[i][j] = 1 の場合、以下の遷移をする。 - dp[i+1][i+a[i]] = 1 - dp[i+1][i+b[i]] = 1

dp[N][S]が1であればYes、そうでないならNo。

また、Yesの場合は、カードの置き方の一例を求める必要があるので、dpをNから逆順にたどっていく。

dp[N-1][S-a[i]] か dp[N-1][S-b[i]] でどちらかは1なので、前者であれば表を選び、後者であれば裏を選ぶ。

void solve(long long N, long long S, std::vector<long long> a, std::vector<long long> b){
    vvl dp(N+9, vl(S+9, 0));
    dp[0][0] = 1;
    REP(i, N) {
        REP(s, S) {
            if (dp[i][s]==0) continue;
            if (s+a[i]<=S) dp[i+1][s+a[i]] = 1;
            if (s+b[i]<=S) dp[i+1][s+b[i]] = 1;
        }
    }
 
    if (dp[N][S]) {
        cout << YES << endl;
        string ans;
        ll n = N;
        ll s = S;
        while (n > 0) {
            if (s >= a[n-1] && dp[n-1][s-a[n-1]]) {
                s -= a[n-1];
                ans.push_back('H');
            } else if (s >= b[n-1] && dp[n-1][s-b[n-1]]) {
                s -= b[n-1];
                ans.push_back('T');
            }
            n--;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    } else {
        cout << NO << endl;
    }
}