■

ABC275F

解法

\(a_{i}\) を残すとき 0, 消すとき 1 として，01 列を考える． 1 が連続している区間の個数を最小化する問題となる．
区間を数える代わりに，[01] の並びを数えると考えるとよい． [11], [00], [10] は数えないとする． つまり，01 列において [01] の並びの個数が 1 の区間の個数と 1対1 対応する．
これを踏まえれば，次の dp が作れる． \(dp_{i,s,k} := \) \(a_{[0,i)}\) において， 合計が \(s\) かつ 最後が \(k \in 2\) のときの min. ここで，\(a_{-1} = 0\) かつ \(-1\) 番目を残すと考えると実装が楽．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n,m;

  cin >> n >> m;

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

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

  dp[0][0] = 0;

  rep(i,n){

    // 1: del

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

    swap(dp,old);

    drep(s,m+1){

      ll t = s + a[i];

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

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

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

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

    }

  }

  rep1(x,m){

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

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

    cout << ans << endl;

  }

 

  return 0;

}