らての精進日記

修行をします

aoj0615:Cake2

解法

区間DPした。
dp[l][r] : 区間[l+1,r-1]まで選び終わったときの残りのケーキでの最大値、とした。

r-l-1の値が奇数か偶数かでどちらが選ぶ番かわかります。奇数のときは妹なので、
A[l] > A[r]ならdp[l][r] = dp[l-1][r]
A[l] < A[r]ならdp[l][r] = dp[l][r+1]
とします。

偶数のときは兄なので、
dp[l][r]=max(dp[l-1][r]+A[l],dp[l][r+1]+A[r])
とします。

答えは、dp[i-1][i+1] + A[i]の最大値です。

円環の問題なので、データを3つ繋げて円環を表現しました。

あと、dpは難しいのでメモ化再帰しました。


JOI本番ではそこそこバグらせてつらかったトラウマのようなものがあったので、なかなか手を出せずにいました。しかし、久々に解いてみたらかなりあっさり解けて感動しました。

本番では円環をmodをとって表現していたり、ほかにもかなりひどい実装をしていたのでわりと成長したかもね。

JOI本戦の2問目としては妥当かも。(当時は3問目と難易度逆だろと思っていた)

コード

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

#define int long long

int N;
int A[6000];

//6000*6000->MLE
int memo[4000][6000];

int dfs(int l,int r){
    if(~memo[l][r])return memo[l][r];

    int ret;
    int cnt=r-l-1;

    if(cnt==N)ret=0;
    else if(cnt&1){
        if(A[l]>A[r])ret=dfs(l-1,r);
        else ret=dfs(l,r+1);
    }
    else{
        ret=max(dfs(l-1,r)+A[l],dfs(l,r+1)+A[r]);
    }

    return memo[l][r]=ret;
}

signed main(){
    cin.tie();
    ios_base::sync_with_stdio(false);

    cin>>N;
    for(int i=0;i<N;i++){
        int a;
        cin>>a;
        A[i]=A[N+i]=A[N*2+i]=a;
    }

    memset(memo,-1,sizeof(memo));

    int ans=0;
    for(int i=0;i<N;i++)ans=max(ans,dfs(N+i-1,N+i+1)+A[i]);

    cout<<ans<<endl;
}