自动搬运

查看原文

来自洛谷，原作者为

	DevilsFlame rp ++

搬运于2025-08-24 22:07:42，当前版本为作者最后更新于2024-10-23 13:03:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一眼典型区间 dp。

关于擦除和得分，我们难想到动归式子：f[i][j] = max(f[i][j],f[i][k] + f[k + 1][j])。可是难点就在于擦除条件。于是草草写下这行代码：

if((i + 1 == j || p[i + 1][j - 1]) && check(a[i],a[j]))
{
	p[i][j] = 1;
	f[i][j] = f[i + 1][j - 1] + b[i] + b[j];
	continue;
}

不难发现，这漏了情况。这里主要难的就是擦除条件。
可是，也是有单调性。f[i][i + 1] 是可以确定的，那么 f[i][i + 2] = max(f[i][i + 1],f[i + 1][i + 2])，但这是奇数的情况。那如果是 f[1][4]？

满足可以让 f[1][4] 完全擦除的有 $2$ 种情况：

1. f[1][2] && f[3][4]
2. f[2][3] && gcd(a[1],a[4]) != 1
   一旦完全擦除，那么这一区间肯定就是最大值。 可以用 bool 数组判断区间是否完全擦除。

#include<bits/stdc++.h>
#define N 805
using namespace std;
long long n,a[N],b[N],f[N][N];
bool g[N][N];//判断该区间是否可擦除 
int gcd(int a,int b)
{
	if(b == 0) return a;
	return gcd(b,a % b);
}
inline bool check(int a,int b)//是否满足提议要求
{
	if(gcd(a,b) == 1) return 0;
	return 1;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i ++) cin >> a[i];
	for(int i = 1;i <= n;i ++) cin >> b[i];
	for(int t = 1;t < n;t ++)//枚举长度(t + 1)
		for(int i = 1;i + t <= n;i ++)//区间左端点
		{
			int j = i + t;//右端点 = i + t
			if(check(a[i],a[j]) && (i + 1 == j || g[i + 1][j - 1]))
            //如果(j - i + 1)是奇数，那么 g[i + 1][j - 1] 肯定为 0 
			{
				g[i][j] = 1;
				f[i][j] = f[i + 1][j - 1] + b[i] + b[j];
				continue;
			}
			for(int k = i;k < j;k ++)//枚举界点
			{
				f[i][j] = max(f[i][k] + f[k + 1][j],f[i][j]);
				if(g[i][k] && g[k + 1][j])//该区间可擦除（分段擦除，例如 2 4 9 15）
				{
					g[i][j] = 1;
					break;
				}
			}
		}
	cout << f[1][n] << endl;
	return 0;
}

该算法不是最优，但很简单易懂，时间复杂度为 $O(n^3)$。