E. Pchelyonok and Segments

我们发现$k\{k\}$可以是答案的前提是线段的长度总和不超过$n\{n\}$。即$\frac{k\ast (k+1)}{2}\le n\backslash frac\{k*(k+1)\}\{2\}\backslash le\; n$，$k\le 447k\backslash le\; 447$

令$d{p}_{i,j}dp\_\{i,j\}$表示长度为$jj$的段的最大和，同时我们已经考虑了后缀$ii$上所有的元素，并且选择了长度为$j,j-1,\mathrm{.}\mathrm{.}\mathrm{.},1\{j,j-1,...,1\}$的段，其中段的总和增加。

1.我们可以在长度为$j\{j\}$的段中包含元数$i\{i\}$：

dp[i][j]=dp[i+1][j]

2.或者包含元素$i\{i\}$，前提是$d{p}_{i+j,j-1}dp\_\{i+j,j-1\}$的值大于段$i,i+1,\mathrm{.}\mathrm{.}\mathrm{.}i+j-1\{i,i+1,...i+j-1\}$上的总和。

dp[i][j]=max(dp[i+1][j],sum[i+j-1]-sum[i-1])

code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+7,inf=1e9+7;
int n,a[maxn],dp[maxn][450];
ll sum[maxn];
inline void solve() {
	cin>>n;
	for(int i=1;i<=n;++i) {
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	int k(0);
	while(k*(k+1)/2<=n) ++k;
	for(int i=1;i<k;++i) dp[n+1][i]=-inf;
	dp[n+1][0]=inf;
	for(int i=n;i;--i) {
		for(int j=0;j<k;++j) {
			dp[i][j]=dp[i+1][j];
			if( j && i+j-1<=n && sum[i+j-1]-sum[i-1]<dp[i+j][j-1] ) {
				dp[i][j]=max(dp[i][j],(int)(sum[i+j-1]-sum[i-1]));
			}
		}
	}
	int ans(0);
	for(int i=1;i<k;++i) if(dp[1][i]>0) ans=i;
	cout<<ans<<'\n';
}
int main() {
	cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
	int _;
	cin>>_;
	while(_--) solve();
	return 0;
}