ps:如果有什么不对，欢迎指正，非常感谢qwq

树状数组优化dp

传送门
首先明确一个事实，每次操作的右端点一定是最后一个位置n,据此我们容易得出这个题目的状态转移方程：
$f[i][j] = max(f[x][y]) + 1, x < i, y <= j, a[x] + y <= a[i] + j.$
其中f[i][j]表示前i个元素，使用j次操作可以得到的最大值.但是如果直接暴力循环的时间复杂度为$O(n^4)$一眼顶针鉴定为寄，所以可以考虑使用一个二维的树状数组进行优化(都是前缀最大值).于是建立一个tr[i][j]的树状数组，用于维护二维前缀最大值.

////洛琪希Daisuki
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define LL long long
#define ULL unsigned long long
#define LD long double
#define PII pair<int, int>
//#define int long long
LL lowbit(LL x) {return x & -x;}
LL gcd(LL a,LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a,LL b) {return a / gcd(a, b) * b;}
//head

const int N = 5505, M = 505;

signed main()
{
    int n, k; cin >> n >> k;
    vector<int> a(n + 10);
    vector<vector<int>> dp(n + 10, vector<int>(k + 10)), tr(M, vector<int>(N));

    auto query = [&](int x, int y) -> int{
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)){
            for (int j = y; j > 0; j -= lowbit(j)){
                ans = max(ans, tr[i][j]);
            }
        }
        return ans;
    };

    auto modify = [&](int x, int y, int d) -> void{
        for (int i = x; i <= M; i += lowbit(i)){
            for (int j = y; j <= N; j += lowbit(j)){
                tr[i][j] = max(d, tr[i][j]);
            }
        }
    };

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ ){
        for (int j = k; j >= 0; j -- ){
            dp[i][j] = query(j + 1, a[i] + j) + 1;//树状数组特性，所有下标向右边移动一个单位。
            modify(j + 1, a[i] + j, dp[i][j]);
        }
    }

    cout << query(k + 1, N) << endl;
}

线段树优化dp

传送门
一般想考你dp优化的题目一般状态表示和状态转移方程不会特别难想
题目大意：
给定一个由n个整数组成的数组a。你应该将a分割成连续的非空子数组（有2^(n-1)种方法可以做到这一点）
令s=a_l+a_{l+1}+…+a_r。子数组a_l, a_{l+1}, …, a_r的值为：

• $(r-l+1)$ 如果$s>0$，
• $0$ 如果$s=0$，
• $-(r-l+1)$ 如果$s<0$。

通过分割，你能够获得的值的最大和是多少？

这题目干的第一件事肯定就是求前缀和，根据条件容易得到下面三个状态转移方程：
$dp[i] = max(dp[j] - j) + i, s[i] > s[j]$
$dp[i] = max(dp[j]), s[i] = s[j]$
$dp[i] = max(dp[j] + j), s[i] < s[j]$
于是我们可以分别建立三棵（两颗的话可以用其他的维护$dp[i]$）线段树分别维护$dp[i] - i$, $dp[i]$, $dp[i] + i$的最值.

于是可以首先对前缀和数组s进行离散化(前缀和的值的覆盖范围太大了，存都要用long long), 把$s[j]$定为下标，查询$s[j]$之前或者之后的区间最大值.

其他的写代码里面了。。。

//洛琪希Daisuki
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define LL long long
#define ULL unsigned long long
#define LD long double
#define PII pair<int, int>
//#define int long long
LL lowbit(LL x) {return x & -x;}
LL gcd(LL a,LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a,LL b) {return a / gcd(a, b) * b;}
//head

struct Val{
    int val = -INF;
};
struct Info{
    int l,r;Val s;
};
Val operator+(const Val &a,const Val &b){
    return {max(a.val,b.val)};
}
Info op(Info a,int b){
    a.s.val = max(a.s.val,b);
    return a;
}
struct SegTree
{
    int n;
    vector<Info> tr;
    SegTree(int n) : n(n){
        tr.resize(n * 4 + 1), build(1, 1, n);
    }
    void build(int u,int l,int r){
        tr[u].l = l,tr[u].r = r;
        if (l != r){
            int mid = (l + r) / 2;
            build(u * 2,l,mid);
            build(u * 2 + 1,mid + 1,r);
            pushup(u);
        }
    }
    void modify(int u,int l,int r,int d){
        if(tr[u].l < l || tr[u].r > r){
            int mid = (tr[u].l  + tr[u].r) / 2;
            if (l <= mid) modify(u * 2,l,r,d);
            if (r > mid) modify(u * 2 + 1,l,r,d);
            pushup(u);
        }
        else tr[u] = op(tr[u],d);
    }
    Val ask(int u,int l,int r){
        if (tr[u].l >= l && tr[u].r <= r)
            return tr[u].s;
        int mid = (tr[u].l + tr[u].r ) / 2;
        Val ans;
        if (l <= mid) ans = ask(u * 2,l,r);
        if (r > mid) ans = ans + ask(u * 2 + 1,l,r);
        return ans; 
    }
    void pushup(int u){
        tr[u].s = tr[u * 2].s + tr[u * 2 + 1].s;
    }
};//区间最值线段树，特别感谢hxd的模板www

void solve(){
    int n; cin >> n;
    vector<LL> a(n + 1), s(n + 1);
    map<LL, int> mp;

    for (int i = 1; i <= n; i ++ ) cin >> a[i], s[i] = s[i - 1] + a[i];
    //离散化, 把所有位置的前缀和按大小排序，其值对应为其下标
    vector<LL> vs(s.begin(), s.end()); sort(all(vs));
    int tot = 0;
    for (auto x : vs){
        if (!mp.count(x)) mp[x] = ++ tot;
    }
    vector<LL> s2(n + 1);
    for (int i = 1; i <= n; i ++ ) s2[i] = mp[s[i]];

    vector<int> dp(n + 1, -INF);//因为最值可能为负数.
    SegTree segtree1(n + 10), segtree2(n + 10), segtree3(n + 10);
    //初始化操作
    dp[0] = 0;//第0个元素的dp值是0
    segtree1.modify(1, mp[0], mp[0], 0), segtree2.modify(1, mp[0], mp[0], 0), segtree3.modify(1, mp[0], mp[0], 0);
    //三棵线段树在前缀和为0时的值全是0

    for (int i = 1; i <= n; i ++ ){
        if (s2[i] > 1) dp[i] = max(dp[i], segtree1.ask(1, 1, s2[i] - 1).val + i);

        dp[i] = max(dp[i], segtree2.ask(1, s2[i], s2[i]).val);

        if (s2[i] < tot) dp[i] = max(dp[i], segtree3.ask(1, s2[i] + 1, tot).val - i);

        segtree1.modify(1, s2[i], s2[i], dp[i] - i);
        segtree2.modify(1, s2[i], s2[i], dp[i]);
        segtree3.modify(1, s2[i], s2[i], dp[i] + i);
    }

    cout << dp[n] << endl;
}

signed main()
{
    IOS;
    int _ = 1; cin >> _;
    while (_ -- ) solve();
    return 0;
}