题解：AT_agc050_b [AGC050B] Three Coins

· · 题解

小巧精致的区间 dp。
首先观察数据范围 3\le n \le 500，发现很适合常规的区间 dp，可以直接敲出来： 

for(int l=2;l<=n;l++)
{
    for(int i=1,j;i<=n-l+1;i++)
    {
        j=i+l-1;
        for(int k=i;k<j;k++)
            dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]);
    }
}

那么然后呢？
我们要考察本题贡献的方式，连续加入三个或者连续去掉三个，显然只是这样过于局限，我们需要更大的性质。
手玩一下：

我们发现，一个圈可以任意左移或者右移 3 的倍数个格子，并且由于只能对三个格子操作，所以每次一定是三个三个加贡献，加贡献的块长也一定是 3 的倍数。
那么在块长为 3 的倍数时，要额外算一下：

dp_{i,j}=max(dp_{i,j},a_i+a_j+a_j+dp_{i+1,k-1}+dp_{k+1,j-1})

注意 k-i-1 与 j-k-1 也必须为 3 的倍数！
完整代码如下：

#include<bits/stdc++.h>
#define int long long
#define db double
#define maxn 1000005
#define mod 1000000007
#define fir first
#define sec second
#define pr pair<int,int>
#define pb push_back
#define mk make_pair
#define inf 10000000000000000
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')WW=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX%10+'0');
}
int T,n,a[maxn],dp[505][505];
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int l=3;l<=n;l++)
    {
        for(int i=1,j;i<=n-l+1;i++)
        {
            j=i+l-1;
            if(l%3==0)
                for(int k=i+1;k<j;k++)
                    if((k-i-1)%3==0&&(j-k-1)%3==0)dp[i][j]=max(dp[i][j],a[i]+a[j]+a[k]+dp[i+1][k-1]+dp[k+1][j-1]);
            for(int k=i;k<j;k++)dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
        }
    }
    write(dp[1][n]);
    return 0;
}