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; }
まとめ
そういえばみんなのプロコンの予選はまだ記事にしてなかったか。