题解：AT_agc050_b [AGC050B] Three Coins

小巧精致的区间 dp。
首先观察数据范围

3\le n \le 500

，发现很适合常规的区间 dp，可以直接敲出来：

CPP

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]);
    }
}

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

.o.... $\to$ .oooo. $\to$ ....o.
....o. $\to$ .oooo. $\to$ .o....

我们发现，一个圈可以任意左移或者右移

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$ 的倍数！
完整代码如下：

CPP

#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;
}

题解：AT_agc050_b [AGC050B] Three Coins

文章操作

相关推荐

评论

题解：AT_agc050_b [AGC050B] Three Coins