Knapsack for All Segments [AtCoder Beginner Contest 159 F]

https://atcoder.jp/contests/abc159/tasks/abc159_f

前提知識

• 動的計画法

解説

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

DPを使ってまとめて数え上げることができる。
思いつく仮定としては、DPで解くんだろうと考え始めることと、N,S≦3000なので、dp[N][S]系だろうで
考えることで思いつく。

dp[i][sm][state] := i番目まで使って、区間の総和がsmで、区間の選択状態がstateのときの組み合わせ
stateは0がNone（区間未選択）、1がL（左端のみ確定している）、2がLR（右端も左端も確定している）
遷移としては、次にどの状態に遷移するかの3択と、その要素を使用するか使用しないかの2択の掛け合わせである。

要素が使用できるのは、状態がLかLRのときで、かつ、前の状態がLRでないときである。
前の状態がLRで、今の状態もLRのときは、それよりも前でRが確定していて、今は範囲外にあるので、
要素を使って総和Kに貢献することはできないためである。

状態遷移は値が小さい方には遷移できない。
あとは、オーバーフローにちょっと注意すること。
dp[N][S][LR]が答えになる。

int N, S, A[3010];
enum { NONE, L, LR };
mint dp[3010][6010][3];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    rep(i, 0, N) cin >> A[i];

    dp[0][0][NONE] = 1;
    rep(i, 0, N) rep(sm, 0, S + 1) rep(state, 0, 3) {
        rep(nxt, state, 3) {
            dp[i + 1][sm][nxt] += dp[i][sm][state];
            if(nxt != NONE && state != LR) dp[i + 1][sm + A[i]][nxt] += dp[i][sm][state];
        }
    }
    cout << dp[N][S][LR] << endl;
}