kmjp's blog

競技プログラミング参加記です

Codeforces ECR #063 : D. Beautiful Array

5月の有志コンラッシュと、TCO・GCJその他で、4月分のCodeforcesすら未消化…。
https://codeforces.com/contest/1155/problem/D

問題

整数列Aと整数Xが与えられる。
このうち1つの部分列の要素をX倍することができる。

X倍後の部分列の和の最大値を求めよ。

解法

以下の問題が参考になる。
D - Ears

和を求める部分列以外の場所はX倍する必要がないので、整数列は以下の順で分割できる。

  • 和を求める部分列の手前
  • 和を求める部分列内で、X倍する前
  • 和を求める部分列内で、X倍する
  • 和を求める部分列内で、X倍した後
  • 和を求める部分列の後

よって、以下をDPで埋めていけばよい。
f(n,s) := n番目までの要素について状態を割り振ったとき、n番目の要素が状態sである場合の総和の最大値

int N,X;
ll dp[303030][5];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	ll ret=0;
	FOR(i,N) {
		cin>>x;
		
		dp[i+1][0]=dp[i][0];
		dp[i+1][1]=max(dp[i][0],dp[i][1])+x;
		dp[i+1][2]=max({dp[i][0],dp[i][1],dp[i][2]})+1LL*x*X;
		dp[i+1][3]=max({dp[i][0],dp[i][1],dp[i][2],dp[i][3]})+x;
		dp[i+1][4]=max({dp[i][0],dp[i][1],dp[i][2],dp[i][3],dp[i][4]});
	}
	cout<<max({dp[N][0],dp[N][1],dp[N][2],dp[N][3],dp[N][4]})<<endl;
	
}

まとめ

そういえばみんなのプロコンの予選はまだ記事にしてなかったか。