卡牌游戏

思路

题目说的是：有 张卡牌排成一排，每次操作可以从最左边选至少 2 张连续卡牌，把它们合并成一张（值为总和），得分加上这个总和。可以随时停止操作，问最大得分是多少。

关键观察：设前缀和 。

第一次合并前 张牌，得分是 。第二次合并当前最左边的若干张（合并后的牌 + 至少一张新牌），得分是 （因为合并后的牌值就是之前的前缀和，加上新牌就是更长的前缀和）。

以此类推，每次操作的得分恰好是某个前缀和 ，而且这些下标构成严格递增序列，起点 。

那问题就变成了：从 中选一个子集，使得对应前缀和之和最大。

这太简单了！每个位置独立决策——前缀和为正就选，为负就不选。

$$

一次遍历搞定， 时间。

用样例验证一下：

  • ，前缀和 ，选 得 ，选 得 ，总分 。正确！
  • ，前缀和 ，只有 和 的前缀和为正（ 和 ），总分 。正确！

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    long long sum=0, ans=0;
    for(int i=0;i<n;i++){
        long long x;
        scanf("%lld",&x);
        sum+=x;
        if(i>=1 && sum>0) ans+=sum;
    }
    printf("%lld\n",ans);
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long sum = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            sum += x;
            if (i >= 1 && sum > 0) ans += sum;
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = 0
    ans = 0
    for i in range(n):
        s += a[i]
        if i >= 1 and s > 0:
            ans += s
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    let sum = 0, ans = 0;
    for (let i = 0; i < n; i++) {
        sum += a[i];
        if (i >= 1 && sum > 0) ans += sum;
    }
    console.log(ans);
});

复杂度

  • 时间复杂度：，一次遍历。
  • 空间复杂度：，只用了常数变量。