E. Pchelyonok and Segments

题意

给定长度为$nn$的数组，要求将数组分成$KK$段，每段连续，并且对于段$ii$和$i+1i+1$，段$ii$的长度要比段$i+1i+1$长$11$, 并且段$ii$的段内元素和要比$i+1i+1$段的小.求最大的$KK$ 首先将数组反向，问题就变成了求长度递增的$KK$段，区间和递减。

得到状态表示$dp[i][j]dp[i][j]$为前i个元素中，最后一段长度为$jj$的最大末尾段和。

有状态转移方程：

$dp[i][j]=dp[i-1][j]dp[i][j]\; =\; dp[i-1][j]$

若$i-j>=1i\; -\; j\; >=\; 1$且，有$dp[i][j]=max(dp[i][j],{\sum }_{i-j+1}^{j}a[i])dp[i][j]\; =\; max(dp[i][j],\; \backslash sum\_\{i-j+1\}^\{j\}a[i])$

这里需要十分注意边界条件

$dp[0][i],i\in [1,M]dp[0][i],\; i\; \backslash in\; [1,\; M]$代表空集里面最后一段长度是$jj$的方案中结尾段的最大值，显然不存在，不可以转移到任何状态，设为$-inf-inf$

$dp[i][0]\mathrm{.},i\in [1,N]dp[i][0].\; ,\; i\; \backslash in\; [1,\; N]$代表前$ii$个里面选0个，任意选$11$的状态都可以从其转移过来，应该设为可以转移的边界，故设为$+inf+inf$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5, M = 450;
#define inf 0x3f3f3f3f3f3f3f3f
ll f[N][M], a[N];
void solve() {
    int n; cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    reverse(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i ++) a[i] += a[i - 1];
    for(int i = 1; i < M; i ++) f[0][i] = -inf;
    for(int i = 0; i <= n; i ++) f[i][0] = inf;
    for(int k = 1; k < M; k ++) {
        for(int i = 1; i <= n; i ++) {
            f[i][k] = f[i - 1][k];
            if(i - k >= 0) {
                if(a[i] - a[i - k] < f[i - k][k - 1])
                    f[i][k] = max(f[i][k], a[i] - a[i - k]);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i < M; i ++) if(f[n][i] > 0) ans = i;
    cout << ans << endl;
}
int main() {
    int t; cin >> t;
    while(t --) {
        solve();
    }
}