割とすんなり解けた回。
https://codeforces.com/contest/1736/problem/E
問題
N要素の整数列Aが与えられる。
N回以下の処理を行う。
- 以下のいずれかを行う。
- 何もしない
- 隣接2要素を1つ選びswapし、その後片方を0にする
- その後、A[i]をスコアに加算する
総スコアの最大値を求めよ。
解法
0にする作業を無視してよい。スコアに加算しない値を0にすれば、総スコアに影響しない。
あとは、i回目の処理までにi回swapできるとして、
dp(n,k) := n要素目までにk回swap使ったときの総スコアの最大値
を求めて行こう。
int N; int A[505]; int from[505][505]; int to[505][505]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; MINUS(from); from[0][1]=0; FOR(i,N) { for(x=i;x>=0;x--) FOR(y,N+1) if(from[x][y]>=0&&y>=i-x) { for(j=x+1;j<=N;j++) { chmax(from[j][y-(i-x)+1],from[x][y]+A[i]*(j-x)); } } } int ret=0; FOR(i,N+2) ret=max(ret,from[N][i]); cout<<ret<<endl; }
まとめ
Div2とはいえ最終問の割にすんなり。