Yukicoder037 遊園地のアトラクション

問題概要

$T$時間遊園地に滞在する。$N$個のアトラクションがあり、それぞれのアトラクションで$C[i]$時間並び$V[i]$の満足度を得る。 同じアトラクションに乗るたびに、$V[i]$は少数切り捨てで半分になる。 $T$時間の遊園地での滞在で最大の満足度を得たいとき、得られる満足度は。

$T\leqq10^4$、$N\leqq15$、$C[i]\leqq10^2$、$V[i]\leqq5*10^2$

yukicoder037

解法

$dp[t]$:=時刻$t$における満足度の最大値　を考える。 あるアトラクションについて$10$回以上は乗れないので、 ある時間について、アトラクションに何回乗るかを一度に遷移させてやれば良い。 これは別々に分けることと一緒で、分けたものも時間が一緒なので、同じ時間幅に対しては 必ず値が高いものが加算されるのが、別々に分けてもいい理由である。

計算量:$O(NTlogV[i])$

ソース

    #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)++)
    #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        LL T, N; cin >> T >> N;
        VI c(N), v(N);
        FOR(i, 0, N) {
            cin >> c[i];
        }
        FOR(i, 0, N) {
            cin >> v[i];
        }
        VI dp(T + 1, 0);
        FOR(i, 0, N) {
            FORR(t, T - 1, 0 - 1) {
                int sumT = 0;
                int sumV = 0;
                int V = v[i];
                FOR(j, 0, 10) {
                    sumT += c[i];
                    sumV += V;
                    V /= 2;
                    if (t + sumT <= T) {
                        dp[t + sumT] = max(dp[t + sumT], dp[t] + sumV);
                    }
    
                }
            }
        }
        int ans = 0;
        FOR(t, 0, T + 1) {
            ans = max(ans, dp[t]);
        }
        cout << ans << "\n";
    
        return 0;
    }