AtCoder Beginner Contest 275F

F - Erase Subarrays

残す場所をo, 消す場所をx と考えて，ox 列を作る．

連続する x のブロックの個数を数えるが，それは ox が連続している場所の個数と一致．

ただし，形式的にの前にo があるものと考える．

としてdp.

typedef long long ll;

const ll INFL = 1LL << 60;

using vll = vector<long long>;  using vvll = vector<vll>;

using pll = pair<ll,ll>;

int main() {

    ll n, m;

    cin >> n >> m;

    vll a(n); rep(i,n) { cin >> a[i]; }

    vvll dp(m+1, vll(2, INFL));

    // o : 1 , x : 0

    dp[0][1] = 0; // rem : init o なので 1

    rep(i,n){

        vvll old(m+1, vll(2, INFL));

        swap(dp, old);

        rep(s,m+1){

            // use a[i]

            ll t = s + a[i];

            if(t <= m) chmin(dp[t][1], old[s][0]);

            if(t <= m) chmin(dp[t][1], old[s][1]);

            // not use a[i]

            chmin(dp[s][0], old[s][1] + 1);

            chmin(dp[s][0], old[s][0]);

        }

       

    }

    rep1(s,m){

        ll ans = min(dp[s][0], dp[s][1]);

        if(ans >= INFL) ans = -1;

        cout << ans << endl;

    }

    return 0;

}