脚本宝典收集整理的这篇文章主要介绍了Codeforces Round #750 (Div. 2) E. Pchelyonok and Segments（DP），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目链接 题意： 长度为(n)的数组(s)，求最大的(k)使得：从数组(s)中能找到(k)个互不相交的子列，满足第(i)个子列的长度为(k-i+1)，且(sum(l_1...r_1) < sum(l_2...r_2)<...<sum(l_k...r_k))

思路： 先反转数组，正向递推。 (dp[i][j])表示当前为第(i)个数结尾且长度为(j)的子段的最大和。 转移方程：

• 第(i)个数不是长度为(j)的子段的结尾，则(dp[i][j]=max(dp[i-1][j], dp[i][j]))。
• 第(i)个数是长度为(j)的子段的结尾，则(dp[i][j]=max(dp[i][j], sum[i]-sum[i-j]))，此时需满足前一子段最大和大于当前子段和，即(dp[i-j][j-1]>sum[i]-sum[i-j])。

code:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#include <set>

#define fi first
#define se second
#define pb push_back
// #define endl "n"
#define debug(x) cerr << #x << ":" << x << endl;
#define all(x) x.begin(), x.end()
#define lowbit(x) x & -x
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
#define ull unsigned long long
#define ll long long

const double eps = 1e-5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

using namespace std;

int s[maxn], n;
ll dp[maxn][550], sum[maxn];

int main(){
    int t;
    scanf("%d", &t);
    while(t --){
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)scanf("%d", &s[i]);
        reverse(s + 1, s + n + 1);
        int k = 1;
        while(k * (k + 1)/2 <= n)k ++;

        for(int i = 1; i <= n; i ++){
            sum[i] = sum[i - 1] + s[i];
            for(int j = 0; j <= k; j ++)dp[i][j] = 0;
            dp[i][1] = s[i];
        }
        int ans = 1;
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j < k; j ++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                if(i - 2 * j + 1 >=0 && dp[i - j][j - 1] > (sum[i] - sum[i - j])) {
                    dp[i][j] = max(dp[i][j], sum[i] - sum[i - j]);
                    ans = max(ans, j);
                }
            }
        }
        debug(ans)
        printf("%dn", ans);
    }
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的Codeforces Round #750 (Div. 2) E. Pchelyonok and Segments（DP）全部内容，希望文章能够帮你解决Codeforces Round #750 (Div. 2) E. Pchelyonok and Segments（DP）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。