問題リンク。
atcoder.jp
サボってtex使ってないので表記が読みにくいかも。
flipする操作を愚直に管理すると、2^N個の状態があるのでかなり筋が悪そう。
とりあえずNが小さいときをシミュレーションする。
- N = 1のとき
A[i]は3個そろってはじめて取得できるので、ans = 0
- N = 2のとき
A[i]は3個そろってはじめて取得できるので、ans = 0
- N = 3のとき
flipするかしないかなので、ans = max(0,A[0]+A[1]+A[2])
- N = 4のとき
端っこを無視して、flipするかしないかなので、ans = max(0,A[0]+A[1]+A[2],A[1]+A[2]+A[3])
- N = 5のとき
端っこを無視して、flipするかしないかなので、ans = max(0,A[0]+A[1]+A[2],A[1]+A[2]+A[3], A[2]+A[3]+A[4])
ここでN=4,5のときを踏まえると、3の倍数じゃないときは端っこ削って良さそうな感じがなんとなくする。
端を削ってN=3のときに帰着できそう。→区間dpっぽい。
半開区間[l,r)に関して、dp[l][r] := [l,r)がまだflipされていない(コインが置かれていない)ときの価値の最大値。と定義してみよう。
もう少しNを試すと
- N = 6のとき
端っこを無視して、flipすると、
ans = max(0,dp[0][3],dp[1][4],dp[2][5],dp[4][6])
でもまだこれだけでは足りてなくて、全flipや、全flipした後一部戻すことも出来るので、
ans = max(0,dp[0][3],dp[1][4],dp[2][5],dp[4][6],A[0]+A[1]+A[2]+A[3]+A[4]+A[5], A[0]+A[4]+A[5], A[0]+A[1]+A[5])
となる。
ここで、dpの定義を再度考えると、N＝5のときに帰着できるところがあるので
ans = max(0, dp[0][3]+dp[3][6], dp[0][5], dp[1][6], A[0] + dp[1][4] + A[4]+A[5], A[0]+A[1] + dp[2][5] + A[5])
一般化して書けそうな感じがしてくる。
とりあえず列を2個に分割するところは全探索で良さそう。そうすることでNが小さいときに帰着できる。
- N = 7のとき
ans = max(0, dp[0][i]+dp[i][7])
7は3の倍数ではないので、N=6のときのように端だけ残すことは出来ず上記の遷移のみ。
- N = 8のとき
N=7のときと同様。
- N = 9のとき
N=6のときの遷移同様に、
A[0]+A[1]+dp[2][8]+A[8], A[0]+dp[1][7]+A[7]+A[8]が考えられる。
端を残して、サイズが3の倍数に中を切った後遷移させるのが何となく見える。
加えて、下記のようなものも可能性としてあり得る。
A[0] + dp[1][4] + A[4] + dp[5][8] + A[8]
サンプルで言うと下記のようなケース。
9 10 -1 -1 -1 10 -1 -1 -1 10
上記ももれなく拾える遷移を考えると、
ans = max(A[0] + dp[1][i] + A[i] + A[i+1][8] + A[8])
と書けそう。ここでiは[1,i)と[i+1,8)のサイズが3の倍数になるような整数。
よって、基本的には2分割。
さらに、3の倍数のときだけ中1マスを決めて、2分割。
のような遷移が考えられる。
これで全状態を満たしているかどうかは、未証明のままだが、とりあえずsubmitするとACが得られる(最悪)
#include <bits/stdc++.h> using namespace std; template <class T> void chmax(T& a, const T b){a=max(a,b);} int N,A[500],dp[500][501]; int inf = 100*500+1; //メモ化再帰 int rec(int l,int r) { //既に計算済ならreturn if(dp[l][r]>-inf) return dp[l][r]; int n = r-l; //nが小さいなら愚直 if(n< 3) return dp[l][r]=0; if(n==3) return dp[l][r] = max(0,A[l]+A[l+1]+A[l+2]); int res = 0; //区間を2分割 for(int i=l+1;i<r;++i) { chmax(res,rec(l,i)+rec(i,r)); } //3の倍数のとき、真ん中1点使って区間を2分割 if(n%3==0) for(int i=l+1;i<r;i+=3) { chmax(res, A[l] + rec(l+1,i) + A[i] + rec(i+1,r-1) + A[r-1]); } return dp[l][r]=res; } int main() { cin.tie(0);ios::sync_with_stdio(false); cin >> N; for(int i=0;i<N;++i) cin >> A[i]; //-infで初期化 for(int i=0;i<N;++i) for(int j=0;j<=N;++j) dp[i][j]=-inf; cout << rec(0,N) << endl; return 0; }
800にしては実装かなり軽いけど、上記以外の遷移がないことを証明しろと言われるとあんまり分からないので、やっぱり難しい。
