题目描述：
游戏的规则是这样的：LJC在纸上写下两个长度均为N的数列A和B，两个数列一一对应。HKE每次可以找两个相邻的数A[i]和A[i+1]，如果它们两个不互质，HKE可以选择得到(B[i]+B[i+1])分，然后擦掉A和B位置上的第i,i+1个数，并把两个序列重新按顺序编号。当所有相邻的数互质时，游戏结束。
HKE想知道他最大得分是多少。
数据范围：
对于30%的数据，N ≤ 20；
对于60%的数据，N ≤ 100；
对于80%的数据，N ≤ 500
对于100%的数据，N ≤ 800, 1 ≤ Ai, Bi ≤ 10^9。
思路：
这个题一开始就没能想到用区间 \(dp\) 的方式去解决问题……所以直接废掉了
我们考虑令 \(dp_{i,j}\) 表示 \([i,j]\) 这段区间能否被消除到无法消除。
然后考虑怎么转移这个方程：
显然如果想要使一段区间 \([i,j]\) 消掉，有两种方式：
- 如果 \(\gcd(a_i,a_j)\neq 1\) 则 \(dp_{i,j}\leftarrow dp_{i+1,j-1}+b_i+b_j\)
- \([i,j]\) 这个区间也可以由两个小区间拼成，所以 \(dp_{i,j}\leftarrow dp_{i,k}+dp_{k+1,j}\)
但是这样的话，我们或许会发现一件事情：在进行第二次操作的时候，似乎没有考虑到最后两个区间相接的数分别是多少。
其实这是不需要去考虑的，因为在我枚举 \(k\) 到相接的位置的时候，我们认为 \([l,k]\) 这段区间是处理好的。所以就不需要了记录这个值了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls i<<1
#define rs i<<1|1
#define pb push_back
#define pt putchar
#define All(a) a.begin(),a.end()
#define T int t;cin>>t;while(t--)
#define rand RAND
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f;
const int maxn=805;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int n;
int a[maxn],b[maxn],dp[maxn][maxn];
int f[maxn];
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
memset(dp,-inf,sizeof(dp));
for(int i=1;i<n;i++){
if(__gcd(a[i],a[i+1])!=1)dp[i][i+1]=b[i]+b[i+1];
}
for(int len=4;len<=n;len+=2){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
if(__gcd(a[i],a[j])!=1)dp[i][j]=max(dp[i][j],dp[i+1][j-1]+b[i]+b[j]);
for(int k=i+1;k<j-1;k+=2)dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
for(int i=1;i<=n;i++){
f[i]=f[i-1];
for(int j=0;j<i;j++)
f[i]=max(f[i],f[j]+dp[j+1][i]);
}
cout<<f[n]<<endl;
return 0;
}