文章目录

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5900

题意：给n对数，一个key，一个value，然后如果相邻的两个key不互质，那么他们就满足条件，就阔消去这两个以获得value（消去之后他左右两个就变得相邻了），问获得的value的最大值是多少？

最开始没注意消去之后旁边的就相邻了，然后就WA了，所以用full[i][j]来记录一下这一段是不是全部都阔以消掉，如果阔以的话那么就有第一种转移：
①：dp[i][j]=max(dp[i][j],dp[i+1][j-1]+cost)
然后就是每一段区间都找一找看有没有新的相邻的两个能够消掉的
②：dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k+2][j]+cost[k][k+1]);
然后就是普通情况的转移，枚举断点，把最优的转移过来
③：dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=300+5;
const int MOD=1e9+7;
LL a[maxn],b[maxn];
LL dp[maxn][maxn];
LL cost[maxn][maxn];//cost[i][j]表示i和j这两个的花费 
bool full[maxn][maxn];//full[i][j]表示[i,j]这段全部都用了 
LL sum[maxn];
int f(int i,int j)
{
	if(__gcd(a[i],a[j])!=1)full[i][j]=1;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int N;
		cin>>N;
		for(int i=1;i<=N;i++)cin>>a[i];
		for(int i=1;i<=N;i++)cin>>b[i],sum[i]=sum[i-1]+b[i];
		memset(cost,0,sizeof cost);
		memset(dp,0,sizeof dp);
		memset(full,0,sizeof full);
		for(int i=1;i<=N;i++)for(int j=i+1;j<=N;j++)if(__gcd(a[i],a[j])!=1)cost[i][j]=b[i]+b[j];
		for(int i=1;i<N;i++)if(__gcd(a[i],a[i+1])!=1)full[i][i+1]=1;
		for(int len=1;len<N;len++)
		{
			for(int i=1;i+len<=N;i++)
			{
				int j=i+len;
				if(full[i+1][j-1])//中间已经消掉了，看两边能不能消掉 
				{
					dp[i][j]=max(dp[i][j],dp[i+1][j-1]+cost[i][j]);
					if(cost[i][j])full[i][j]=1;
				}
				for(int k=i;k<j;k++)//找还有没有相邻的两个阔以消掉的 
				{
					dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k+2][j]+cost[k][k+1]);
				}
				for(int k=i;k<j;k++)//转移最优的 
				{
					dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
					if(dp[i][k]==sum[k]-sum[i-1])f(i,k);
					if(dp[k+1][j]==sum[j]-sum[k])f(k+1,j);
					if(full[i][k]&&full[k+1][j])full[i][j]=1;
				}
			}
		}
		cout<<dp[1][N]<<endl;

	}
}