AGC050-B Three Coins

B - Three Coins

解法

区間dpをすると良さそう

dp[l][r][0]:コインの無い区間[l,r)を渡された時の最大値
dp[l][r][1]:コインだけの区間[l,r)を渡された時の最大値

遷移

1.

操作が出来ないのでそのまま

2.

2.1が3で割り切れない

区間の分割を全部試す

2.2が3で割り切れる

2.1に加えて区間上のコインを反転したものも考える

実装

再帰で書いたらTLEしたので区間の長さが短い順に求める形で書いた

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)

const int INF=1e9;
int dp[505][505][2],n,v[505];
//dp[l][r][c]:区間[l,r),(c=1?全部コイン:コイン無し）の状態で渡された時の最大値

template<typename T>
void chmax(T &a,T b){
  if(a<b)a=b;
}

int main(){
  cin>>n;
  REP(i,n)cin>>v[i];
  
  for(int d=1;d<=n;d++)//区間の幅
    for(int l=0,r=d;r<=n;l++,r++)//[l,r)を調べる r=l+d
      REP(c,2)//コインあるか
        if(d<3)for(int i=l;i<r;i++)dp[l][r][c]+=v[i]*c;//幅が3未満なら操作出来ない
        else{
          dp[l][r][c]=-INF;
          for(int i=l+1;i<r;i++)chmax(dp[l][r][c],dp[l][i][c]+dp[i][r][c]);//どこで分けるか
          if((r-l)%3==0)//区間が3の倍数ならコインの状態反転させられる
            for(int i=l+1;i<r;i++)chmax(dp[l][r][c],dp[l][i][c^1]+dp[i][r][c^1]);
        }
        
  cout<<dp[0][n][0]<<endl;
}

atcoder.jp