hihoCoder 1821 : 取卡片游戏

你的名字 2022-05-13 05:30 252阅读 0赞

#### 题目要求 ####

小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;
    }