ABC 031 C - 数列ゲーム
問題概要
省略
解法
いわれたとおりにシミュレーションを行う問題。高橋君の位置を固定して、その時に青木君が丸を付ける場所を探し、その時高橋君の得点を記録しておく。これを高橋君が選べるすべての場所について調べ、高橋君の得点が最大となるときが答えとなる。
ミス
なし。
コード
#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; }