終わってみるとコードは短い問題。
http://codeforces.com/contest/442/problem/C
問題
N要素の数列A[i]が与えられる。
ここから、要素を1個ずつN回抜き出すことを考える。
要素を1個抜き出すと、前後の要素のうち小さい方の数値分、スコアが増える。
なお、数列の両端を抜き出す場合はスコアは増えない。
抜き出す順を最適化し、スコアを最大化せよ。
解法
数列の要素が A[i] => A[i+1] <= A[i+2]と下に凸になっている箇所を考える。
この場合、A[i+1]を最後に取り除くと、A[i]やA[i+2]を取り除いて得られるスコアはmin(A[i-1],A[i+1])やmin(A[i+1],A[i+3])である。
一方、A[i+1]を先に取り除くと、A[i]やA[i+2]を取り除いて得られるスコアはmin(A[i-1],A[i+2])やmin(A[i],A[i+3])であり、こちらの方が多い。
よって数列A[i]を端から見ていって、A[i] => A[i+1] <= A[i+2]となっている箇所があればA[i+1]を取り除く、ということを行う。
すると、残る数列B[i]はB[0] <= B[1] <= ... <= B[p-1] <= B[p] >= B[p+1] >= ... >= B[q-1]と上に凸な形になる。
個の状態で数値の大きい順に取り除くと、B[0]~B[q-1]のうち最大値2個を除いた要素の分スコアに入る。
上記処理はA[i]で下に凸な箇所を探すのにO(N)、B[i]の最大値2個を探すのにO(N)ないしO(N*logN)かかる。
int N; vector<int> V; void solve() { int f,i,j,k,l,x,y; ll ret=0; cin>>N; FOR(i,N) { cin>>x; while(V.size()>=2 && V[V.size()-2]>=V[V.size()-1] && x>=V[V.size()-1]) { ret+=min(V[V.size()-2],x); V.pop_back(); } V.push_back(x); } sort(V.begin(),V.end()); for(i=1;i<V.size()-1;i++) ret+=V[i-1]; cout << ret << endl; }
まとめ
終わってみるとあっさりだが、これ本番中には思いつかないなぁ。