选拔赛第一场（木棒游戏）

链接：无
题目描述：
丢丢陈和陈丢丢在玩♂木棒游戏，一共有 nnn 个木棒，每根木棒都有自己的长度。

游戏的每次操作必须把最左边的连续 (2≤m≤n) 根木棒合并为一根长度为原 m 根木棒长度之和的木棒后将新生成的木棒放在最左侧(原来的 m 根木棒消失)，同时操作者将得到与这根新生成木棒长度相同的分值。

丢丢陈和陈丢丢轮流进行操作，当只剩一根木棒时游戏结束。假设丢丢陈先手，并且他们采用了最优方案操作(使得分数之差最大的方案)，那么丢丢陈的分数减去陈丢丢的分数的最大值是多少呢？

丢丢陈和陈丢丢觉得普通的木棒在侮辱他们的智商，所以决定在游戏中添加了一些长度为非正数的虚拟木棒，混在普通木棒中，游戏规则不变。

输入：
3
2 4 8
4
1 -7 -2 3
输出：
14
-3

思路：做了这个题后感觉自己的dp是学的真的垃圾，只能抄抄别人分析好的状态然后做题，自己拿到题却不知道该怎么去建立状态，首先发现选到哪根得分总和只跟前缀和有关，跟怎么拿到那个状态是没有关系的。那么我们考虑建立状态，表示当前木棍到最后得分相差的最大值，必须要从后向前（如果从前向后不知道后面的做法不能得知最优分数是多少，所以必须从后向前），那么从后面向前面转移就是取后面所有状态中得分最小的，用当前得分减分对手得分最大值的最小值，那么我们可以将这个值用最大值维护，每向前推一次就更新这个最大值，到最后就是结果（多思考一下！换个风格用java写一下）
代码：

import java.util.Scanner;

public class stickgame {
    static int maxn = 200000+100;
    static int a[] = new int[maxn];
    static long S[] = new long[maxn];
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int n;
        while(scan.hasNext()) {
            n = scan.nextInt();
            S[0] = 0;
            for(int i=1;i<=n;i++) {
                a[i] =  scan.nextInt();
                S[i] = S[i-1] + a[i];
            }
            long maxv = S[n];
            for(int i=n;i>=3;i--) {
            maxv = Math.max(maxv,S[i-1] - maxv);
            }
            System.out.println(maxv);
        }
    }
}