今天上午的第十题。

暴力 DP 是简单的，$O(n^2 k)$。
然后我发现每次更新相当于求一段区间和，然后很开心地写了一个线段树优化 DP。

#include <bits/stdc++.h>
using namespace std;
const int N = 115, M = 1e5 + 15, mod = 1e9 + 7;
int n, k, a[N], dp[M];
struct Tree {
    int l, r;
    int sum;
} tr[M << 2];
void pushup(int u) {
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        if (l == 0) tr[u].sum = 1;
        else tr[u].sum = 0;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void change(int u, int x, int d) {
    if (tr[u].l == tr[u].r) {
        tr[u].sum = d;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) change(u << 1, x, d);
    else change(u << 1 | 1, x, d);
    pushup(u);
}
int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;
    if (l <= mid) res += query(u << 1, l, r);
    if (r > mid) (res += query(u << 1 | 1, l, r)) %= mod;
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 0, 100000);
    for (int i = 1; i <= n; i++)
        for (int j = k; j >= 0; j--) {
            int l = max(j - a[i], 0), r = j;
            change(1, j, query(1, l, r));
        }
    printf("%d\n", query(1, k, k));
    return 0;
}

然后由于带了一个 $\log$ 被卡掉了。
原地崩溃，发现可以直接前缀和优化。
对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起，对不起。

#include <bits/stdc++.h>
using namespace std;
const int N = 115, M = 1e5 + 15, mod = 1e9 + 7;
int n, k, a[N], dp[M], s[M];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        s[0] = dp[0];
        for (int j = 1; j <= k; j++) s[j] = (s[j - 1] + dp[j]) % mod;

        for (int j = k; j >= 0; j--) {
            int l = max(j - a[i], 0), r = j;
            if (l) dp[j] = (s[r] - s[l - 1] + mod) % mod;
            else dp[j] = s[r];
        }
    }
    printf("%d\n", dp[k]);
    return 0;
}