B. Just Eat It! CodeForces1285B

佚名 4年前 (2020-01-18) 随笔 1321人围观抢沙发百度已收录

题意：给你一个序列，他的序列和是否大于他的任何他的子序列（连续的子序列）的和。

题目链接：https://vjudge.net/problem/CodeForces-1285B

思路：求他的最大连续子序列和。那如何求最大子序列和呢？用动态规划求即可。但是要注意的是，子系列不能和原序列一样。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

用dp[i]表示以a[i]结尾的最大连续子序列，则容易列出动态转移方程dp[i] = max{dp[i - 1] + a[i], a[i]};

分别求[0, n-1)和[2,n-1]的最大连续子序列和就可以了

#include<iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll a[N] = {0};
int main()
{
    int t;
    scai(t);
    while (t--)
    {
        int n;
        scai(n);
        ll sum = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%lld", &a[i]);
            sum += a[i];
        }

        ll ans = 0;
        string s = "YES";
        for (int i = 0; i < n; ++i)
        {
            ans += a[i];
            if (ans >= sum && i != n-1)
                {s = "NO";break;}
            if (ans  < 0) ans = 0;
        }
        ans = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            ans += a[i];
            if (ans >= sum && i != 0)
                {s = "NO";break;}
            if (ans < 0) ans = 0;
        }
        cout << s <<endl;
    }
}