E. Pchelyonok and Segments
题意
思路
可以从右往左考虑，即从 n 开始 选择长度为 1、2、3 … k 的不相交子段 使得这些子段内元素的和严格递减，求最大的 k。
设dp[i][j] 表示以第i 个数结尾（从右往左看）长度为j 的子段中，元素和的最大值。
那么转移时，会有两种情况：
为什么 dp[i][j] 要维护的是最大值呢？因为从右往左 子段内的元素和要递减，右边的子段和越大，左边符合条件的情况越多。
具体细节见代码。
代码
// Author：zzqwtcc // Problem: E. Pchelyonok and Segments // Contest: Codeforces - Codeforces Round #750 (Div. 2) // Time：2021-10-25 13:52:59 // URL: https://codeforces.com/contest/1582/problem/E // Memory Limit: 512 MB // Time Limit: 2000 ms #include<bits/stdc++.h> #include<unordered_map> #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) // #define debug(x,y) cerr << (x) << " == " << (y) << endl; #define endl '\n' using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } template<typename S,typename T>void debug(S s, T t){cerr << s << " == " << t << endl;} template<typename T>void debug(T t){cerr << t << endl;} template<typename T>void debug(T t[],int st,int ed){for(int i = st; i <=ed;++i){cerr << t[i] << " ";}cerr << endl;} template<typename T>void debug(const vector<T>&t){for(int i =0 ; i < t.size();++i)cerr << t[i] << " ";cerr << endl;} // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 1e5 + 10; int n; int a[N]; int dp[N][505]; int sum[N]; void solve() { cin >> n; // 初始化 for(int i = 1; i <= n;++i){ for(int j = 1; j <= 500;++j){ dp[i][j] = 0; } } // 预处理前缀和 for(int i = 1; i <= n;++i)scanf("%lld",&a[i]),sum[i] = sum[i - 1] + a[i]; // 从右往左开始 dp[n][1] = a[n]; // 无论如何 k都可以为1 int res = 1; for(int i = n - 1;i >= 1;--i){ // 更新长度为 1 的子段的最大值 dp[i][1] = max(dp[i + 1][1], a[i]); for(int j = 2; j <= 500;++j){ // 不选当前这个数 dp[i][j] = dp[i + 1][j]; // 选当前这个数 if(i + j <= n && dp[i + j][j - 1] && sum[i + j - 1] - sum[i - 1] < dp[i + j][j - 1]){ // 更新dp的最大值 dp[i][j] = max(dp[i][j],sum[i + j - 1] - sum[i - 1]); // 如果满足条件 更新答案 res = max(res,j); } } } cout << res << endl; } signed main() { int _; cin >> _; while (_--) solve(); return 0; }
