题目传送门

题意简介：

IOI 酱和 JOI 君分享同一块蛋糕，分享的方式是先从蛋糕上切下来任意一块，然后轮流每一次只能从切口两侧取相邻的蛋糕，IOI 酱很贪心，每次只取两侧最大的那块，而 JOI 君会动态规划，会思考后取两侧的任意一块。

现在，给定蛋糕的份数与每一块蛋糕的大小，求 JOI 君最多能取到多少蛋糕。

思路与代码：

读完题后，感觉非常像区间动态规划问题，但是由于蛋糕是圆形的，怎么办呢？

我们可以将圆形的蛋糕展开，并按照顺序摆成一排，但是这样的话首尾不能相顾，所以我们可以将摆好的蛋糕再摆一次，这样对于 $n$ 块蛋糕，我们就得到了一个长度为 $2n$ 的序列，那么任意连续的 $n-1$ 块蛋糕，都对应了原蛋糕上的一段弧。

确定了区间，我们就可以利用双方博弈的策略进行状态转移。具体的，令 $dp_j(l,r)$ 表示当前剩余区间为 $[l,r]$ 时，JOI 君能获取的最大蛋糕总和，$dp_i(l,r)$ 同理，表示当前剩余区间为 $[l,r]$ 时，IOI 酱能获取的最大蛋糕总和。

所以，当蛋糕轮到 JOI 君取时，他可以任选，转移方程如下：

$$dp_j(l,r)=\max (a_l+dp_i(l+1,r),a_r+dp_i(l,r-1))$$

当蛋糕轮到 IOI 酱取时，她只取最大，需要注意的是，由于每块蛋糕的大小都不相同，JOI 君技术好差，所以无需考虑大小相同的情况，故转移方程如下：

$$dp_i(l,r)=\begin{cases} dp_j(l+1,r) & a_l>a_r \\ dp_j(l,r-1) & a_l<a_r \end{cases}$$

特别的，区间长度为一时，总有：

$$dp_j(l,l)=a_l$$ $$dp_i(l,l)=0$$

最后遍历枚举 JOI 君初始选择的蛋糕块，此时剩余区间为$[i+1,i+n-1]$，然后对应是 IOI 酱的回合，所以答案就是：

$$\max_{i=1}^n(a_i+dp_i(i+1,i+n-1))$$

这样做的时间复杂度是 $O(n^2)$，空间复杂度是 $O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<ll> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n==1)
    {
        cout<<a[1];
        return 0;
    }
    int m=n*2;
    vector<ll> tpa(m+1);
    for(int i=1;i<=m;i++) tpa[i]=a[(i-1)%n+1];
    int row=n+2;
    int col=m+2;
    vector<ll> dpi(row*col,0);
    vector<ll> dpj(row*col,0);
    auto cnt=[col](int l, int r) {return l*col+r;};
    for(int i=1;i<=n-1;i++)
    {
        for(int l=1;l<=n;l++)
        {
            int r=l+i-1;
            if(i==1)
            {
                dpj[cnt(l,r)]=tpa[l];
                dpi[cnt(l,r)]=0;
            }
            else
            {
                //IOI酱的回合
                if(tpa[l]>tpa[r])
                {
                    int tl=l+1,tr=r;
                    if(tl>n)
                    {
                        tl-=n;
                        tr-=n;
                    }
                    dpi[cnt(l,r)]=dpj[cnt(tl,tr)];
                }
                else
                {
                    int tl=l,tr=r-1;
                    dpi[cnt(l,r)]=dpj[cnt(tl,tr)];
                }
                //JOI君的回合
                int llft=l+1,rlft=r;
                if(llft>n)
                {
                    llft-=n;
                    rlft-=n;
                }
                int lrgt=l,rrgt=r-1;
                ll left=tpa[l]+dpi[cnt(llft,rlft)];
                ll right=tpa[r]+dpi[cnt(lrgt,rrgt)];
                dpj[cnt(l,r)]=max(left,right);
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        int tl=(i%n)+1,tr=tl+n-2;
        ll cur=a[i]+dpi[cnt(tl,tr)];
        if(cur>ans) ans=cur;
    }
    cout<<ans;
    return 0;
}

作者的话：

这篇题解是本蒟蒻首次使用 \begin 写题解，如果有观感上的问题可以评论区聊聊喔。求过qwq