本文共 1064 字，大约阅读时间需要 3 分钟。

一眼绝对像区间$dp$

定义$f[i][j]$为区间$[i,j]$的最大收益

可以枚举一个$k$转移$f[i][k]+f[k+1][j]$

而当$a[i]$和$a[j]$不互质时也可能可以消除

但是状态并没有说明$[i+1,j-1]$是否被取空

但是!!如果$f[i+1][j-1]$等于$[i+1,j-1]$的所有价值说明取空了

就可以转移了

#include 
   
    using namespace std;#define int long longconst int maxn = 309;int t,n,a[maxn],b[maxn],f[maxn][maxn],pre[maxn];int gcd(int a,int b){
   	return b==0?a:gcd(b,a%b); }signed main(){
   	cin >> t;	while( t-- )	{
   		cin >> n;		for(int i=1;i<=n;i++)	cin >> a[i];		for(int i=1;i<=n;i++)	cin >> b[i],pre[i]=pre[i-1]+b[i];		for(int l=2;l<=n;l++)		for(int i=1;i+l-1<=n;i++)		{
   			int j = i+l-1;			f[i][j] = max( f[i+1][j],f[i][j-1] );			if( gcd( a[i],a[j] )>1&&pre[j-1]-pre[i]==f[i+1][j-1] )				f[i][j] = max( f[i][j],f[i+1][j-1]+b[i]+b[j] );			for(int k=i;k<=j-1;k++)				f[i][j] = max( f[i][j],f[i][k]+f[k+1][j] );		}		cout << f[1][n] << endl;		memset( f,0,sizeof(f) ); 	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109731784 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！