読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ABC 031 C - 数列ゲーム

abc シミュレーション 全探索

問題

問題概要

省略

解法

いわれたとおりにシミュレーションを行う問題。高橋君の位置を固定して、その時に青木君が丸を付ける場所を探し、その時高橋君の得点を記録しておく。これを高橋君が選べるすべての場所について調べ、高橋君の得点が最大となるときが答えとなる。

ミス

なし。

コード

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
const int INF = 1e9;

int n, a[60];
int main(void){
    cin >> n;
    rep(i, n) cin >> a[i];

    int ans = -INF;
    for (int i = 0; i < n; ++i){//takahashi
        int aoki_p, aoki_v = -INF, tmp_ans;
        for (int j = 0; j < n; ++j){//aokiがよい位置を探す
            if(i == j) continue;
            int l = min(i, j);
            int r = max(i, j);
            int cnt = 1, taka = 0, aoki = 0;
            for (int p = l; p <= r; ++p){
                if(cnt % 2 == 1){
                    taka += a[p];
                }else{
                    aoki += a[p];
                }
                cnt++;
            }
            //aokiが最高得点をとれるときをさがす
            if(aoki > aoki_v){
                aoki_p = j;
                aoki_v = aoki;
                tmp_ans = taka;//青木が最高得点となるときが、高橋の得点
            }
        }
        ans = max(ans, tmp_ans);
    }

    printf("%d\n", ans);
    return 0;
}