彩蛋

由于是日常模拟赛，就没有特意去卡各种假贪心，能过多少随缘。

暴力

一个指数暴力，可以拿$30$分。

#include <bits/stdc++.h>
#define ll long long
#define maxn 505
#define mod 998244353
using namespace std;
int n;
int vis[1<<20],g[21][21],a[21];
int best=0;
void dfs(int sta,int now)
{
	best=max(best,now);
	if (vis[sta]) return;
	vis[sta]=1;
	int pre=-1;
	for (int i=0;i<n;i++) 
	if ((sta>>i)&1)
	{
		if (pre==-1) pre=i;
		else
		{
			if (g[pre][i]>1) 
			{
				dfs(sta^(1<<pre),now+1);
				dfs(sta^(1<<i),now+1);
			}
			pre=i;
		}
	}
}
int main()
{
	cin>>n;
	for (int i=0;i<n;i++) cin>>a[i];
	for (int i=0;i<n;i++) for (int j=i;j<n;j++) g[i][j]=g[j][i]=__gcd(a[i],a[j]);
	dfs((1<<n)-1,0);
	cout<<best<<endl;
}

正解

我们考虑最终序列的形态，一定是xxxoooxooxoxoxoooxoooxooox类的。

其中，x表示这个位置被删掉了，o表示这个位置留下来了。

考虑到这个，我们就可以先预处理一个数组$ok_{l,r}$，表示能否把区间$[l,r]$的元素全都删掉。

此处隐含了一个信息是：我们假设此时$l-1,r+1$没有被删掉。

那么$ok_{l,r}=\max(ok_{l,k-1}\&ok_{k+1,r}\&[gcd(a_k,a_{l-1})>1 \ \ or\ \ gcd(a_k,a_{r+1})>1])$

接下来就可以直接dp了：

$dp_i$表示我留下了$i$，前$i$个元素中最多能留多少个元素。

$dp_i=\max (dp_j+(i-j-1))...ok_{j+1,i-1}$。

通过预处理$gcd$数组可以做到$O(n^3)$的复杂度。

#include <bits/stdc++.h>
#define ll long long
#define maxn 505
#define mod 998244353
using namespace std;
int n;
int a[maxn],g[maxn][maxn],ok[maxn][maxn];
int dp[maxn];
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i]; a[0]=a[n+1]=1;
	for (int i=0;i<=n+1;i++) for (int j=i;j<=n+1;j++) g[i][j]=g[j][i]=__gcd(a[i],a[j]);
	for (int l=1;l<=n+1;l++) ok[l][l-1]=1;
	for (int len=1;len<=n;len++)
	for (int l=1;l+len-1<=n;l++)
	{
		int r=l+len-1;
		for (int k=l;k<=r;k++)
		if (g[l-1][k]!=1 || g[r+1][k]!=1)
		if (ok[l][k-1] && ok[k+1][r])
			ok[l][r]=1;
//		if (ok[l][r]) cout<<l<<" "<<r<<endl;
	}
	memset(dp,-1,sizeof(dp));
	dp[0]=0;
	for (int i=0;i<=n;i++)
	if (dp[i]!=-1)
	{
		for (int j=i+1;j<=n+1;j++)
		if (ok[i+1][j-1])
			dp[j]=max(dp[j],dp[i]+(j-i-1));
	}
//	for (int i=0;i<=n+1;i++) cout<<dp[i]<<" ";
	cout<<dp[n+1]<<endl;
}