hihoCoder 1821 : 取卡片游戏

题目要求

小Hi和小Ho在玩一种游戏。他们面前有N张卡片，每张卡片上都写有一个整数，依次是A1, A2, … AN。

他们可以轮流从中取卡片。每次可以取出1、2或3张卡片(不能不取)，取走的卡片不能被再次拿取，直到最后一张卡片被取走。

这时小Hi和小Ho各自取走的卡片上的整数之和就是他们的得分。

假设小Hi和小Ho都足够聪明，都会选择使自己得分最高的策略。请你计算先手的小Hi最多能得几分。

输入
第一行包含一个整数N。

第二行包含N个整数A1, A2, A3, … AN。

1 ≤ N ≤ 100000

-1000000 ≤ Ai ≤ 1000000

输出
输出小Hi最多的得分

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>

//#include <bits/stdc++.h>
//有了上面这个东西 只要支持的oj就不用再手写上面的这些头文件的包含省事

using namespace std;

// static int x=[](){
// std::ios::sync_with_stdio(false);
// cin.tie(NULL);
// return 0;
// }();


int main() {
    std::ios_base::sync_with_stdio(false);
    //解除cout和scanf的
    int N = 0;
    cin >> N;
    if(N==0) return 0;

    vector<int> v;
    int a = 0;
    while(N&&cin>>a) {
        v.push_back(a);
        --N;
    }
    N = v.size();

    sort(v.begin(),v.end());

    vector<long long> dp(N,0);
    vector<long long> sum(N,0);
    sum[0] = v[0];
    dp[0] = v[0];

    for(int i=1;i<N;++i) {
        sum[i] = sum[i-1] + v[i];
        long long t1 = INT_MIN,t2 = INT_MIN,t3 = INT_MIN;
        t1 = v[i] + sum[i-1] - dp[i-1];
        if(i>=2)
            t2 = v[i] + v[i-1] + sum[i-2] - dp[i-2];
        if(i>=3)
            t3 = v[i] + v[i-1] + v[i-2] + sum[i-3] - dp[i-3];
        dp[i] = max(t1,max(t2,t3));
    }

    cout << dp[N-1] << endl;

    return 0;
}