hdu 5900 QSC and Master

2024-03-02 08:48

文章标签 hdu master 5900 qsc

本文主要是介绍hdu 5900 QSC and Master，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目链接：

题目链接：

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;}
}