[ABC159] F - Knapsack for All Segments

[Q] F - Knapsack for All Segments

考察
1. DP[N][S]とエスパー。
2. indexを進めるごとに、どれだけパターンが増えるかを考える
3. 取りたいindexの、1個前の値を含んだ範囲と、今のindexを接続できる。

1 2 3 4 を考える。

4をとるとき、
(1,2,3)+4と
(2,3)+4と
(3)+4と
+4
の4通りの範囲の取り方が、新しいパターンになる。
連続した範囲で選ぶ必要があるから、1個前のindexをとる取り方を、DPでメモしておけばいい。

例に当てはめると

3 3
1 2 3
を考える。

・1 のとき
DP[1] = 1

・1 2 のときに、どれだけ増える？
(1, 2)の取り方と
(2)の取り方の2通りが増える。
DP[1] = 1
DP[2] = 2
DP[3] = 1

※(1)の取り方はここに含めない。
DPに含めると、次のindexで(1, 3)という飛んだ飛び方を採用してしまうため。

・1 2 3のときに、どれだけ増える？
(1, 2, 3)の取り方と
(2, 3)の取り方と
(3)の取り方の3通りが増える。

増加の仕方は3つのパターンに分けられる。
1. 3を取らない場合、前DPの増加分がそのまま増える
DP[1] = 1
DP[2] = 2
DP[3] = 1

2. 3をとる場合、前DPのすべての状態に+3したものが増える。
DP[4] = 1
DP[5] = 2
DP[6] = 1

2. 3をとる場合のうち、3だけ選ぶ場合がindex通り(3通り)増える。
DP[3] = 3

以上まとめて
DP[1] = 1
DP[2] = 2
DP[3] = 4
DP[4] = 1
DP[5] = 2
DP[6] = 1

※(1), (1, 2), (2) の取り方はここに含めない。
次のDPがあったとして、(X, 4)とすると、飛んでしまうため。

答えは、
index-2のときにDP[3] = 1
index-3のときにDP[3] = 4
あわせて5が答え。

実装

int main() {
  cincout();

  ll N, S;
  cin >> N >> S;

  // DP[N][S]
  vector<vector<mint>> DP(N + 1, vector<mint>(S + 1, 0));

  mint ans = 0;
  for(ll i = 1; i <= N; ++i){
    ll a;
    cin >> a;
    rep(s, S + 1){
      // 1. index-iを含む範囲をとるけど、aは取らない
      DP[i][s] += DP[i - 1][s];
    }
    rep(s, S + 1 - a){
      // 2. index-iを含む範囲をとるし、aを必ず採用する場合
      DP[i][s + a] += DP[i - 1][s];
    }
    // 3. index-iでaがi通りとれる。
    if (a <= S){
      DP[i][a] += i;
    }
    ans += DP[i][S];
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc159/submissions/47643452