Codeforces #825 : Div2 E. Swap and Take

割とすんなり解けた回。
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とはいえ最終問の割にすんなり。