题解 P6625 【[省选联考 2020 B 卷] 卡牌游戏】

Cripple_Abyss · 2020-06-24 22:46:06 · 题解

题目传送门

这可是省选题呀！！！早知道我也去报名了（但是我报不了QwQ）

题目本质：

• 取若干个前缀和，使他们的和最大

题目做法：

• 暴力枚举：如果前缀和大于0，则累加

注：第一个数的前缀和（也就是它本身）不加

时间复杂度：O(n)

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,x,s,n;//注意开long long
int main() {
    cin>>n;
    for (ll i=1; i<=n; i++) {
        cin>>x;
        s+=x;
        if (s>0&&i!=1) 
            ans+=s;
    }
    cout<<ans;
    return 0;
}

都看到这里了，点个赞呗QwQ