【HDU - 5900】QSC and Master（区间dp）

题干：

Every school has some legends, Northeastern University is the same.

Enter from the north gate of Northeastern University，You are facing the main building of Northeastern University.Ninety-nine percent of the students have not been there，It is said that there is a monster in it.

QSCI am a curious NEU_ACMer，This is the story he told us.

It’s a certain period，QSCI am in a dark night, secretly sneaked into the East Building，hope to see the master.After a serious search，He finally saw the little master in a dark corner. The master said：

“You and I, we're interfacing.please solve my little puzzle！

There are N pairs of numbers，Each pair consists of a key and a value，Now you need to move out some of the pairs to get the score.You can move out two continuous pairs，if and only if their keys are non coprime(their gcd is not one).The final score you get is the sum of all pair’s value which be moved out. May I ask how many points you can get the most？

The answer you give is directly related to your final exam results~The young man~”

QSC is very sad when he told the story，He failed his linear algebra that year because he didn't work out the puzzle.

Could you solve this puzzle?

（Data range：1<=N<=300
1<=Ai.key<=1,000,000,000
0<Ai.value<=1,000,000,000）

Input

First line contains a integer T，means there are T(1≤T≤10) test case。

Each test case start with one integer N . Next line contains N integers，means Ai.key.Next line contains N integers，means Ai.value.

Output

For each test case,output the max score you could get in a line.

Sample Input

Sample Output

0
2
0

题目大意：

给一串数的key和value，如果相邻两元素key不是互质的就可以将这俩移除并获得这俩的value值，移除后两侧的元素便是相邻了，问最终最大能获得多少value值。

每次合并两个数之后，这两个数就会消失，然后旁边的数会接上。比如3 2 4 6 合并了 2 4 则剩下3 6也可以合并

解题报告：

是石子合并那道题的晋升版，，稍微改一改就可以了、、采用先继承后扩展的方式写、、不难想出来（话说还是对区间dp不是很熟啊刚开始就乱搞一通、、想明白了其实就很简单了）

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 500 + 5;
int n;
ll dp[MAX][MAX];
bool bk[MAX][MAX];
ll a[MAX],val[MAX];
ll sum[MAX];
int main() {
	int t;
	cin>>t;
	while(t--) {
		memset(dp,0,sizeof dp);
		memset(sum,0,sizeof sum);
		scanf("%d",&n);
		for(int i = 1; i<=n; i++) scanf("%lld",a+i);
		for(int i = 1; i<=n; i++) scanf("%lld",val+i),sum[i] = sum[i-1]+val[i];
		for(int i = 1; i<n; i++) {
			if(__gcd(a[i],a[i+1])>1) {
				bk[i][i+1]=1,dp[i][i+1]=val[i]+val[i+1];
			}
			bk[i][i]=1;//dp[i][i]=val[i];
		}
		for(int len=3; len<=n; len++) {
			for(int l=1; l<=n-len+1; l++) {
				int r=l+len-1;
				for(int k = l; k<r; k++) {
					dp[l][r] = max(dp[l][r],dp[l][k]+dp[k+1][r]);
					
				}
				if(dp[l+1][r-1] == sum[r-1]-sum[l] && __gcd(a[l],a[r])>1) {
					dp[l][r] = max(dp[l][r],dp[l+1][r-1] + val[l] + val[r]);
				}
			}
		}
		printf("%lld\n",dp[1][n]);
	}
	return 0 ;
}

附另一种写法：

区间DP，区间长度为1时dp[i][i]为0，添加一个标记数组vis[i][j]，记录区间内是否所有数字都为可以移除，每次处理需要讨论最后留下区间两侧的情况。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int key[505],val[505],n;
bool vis[505][505];//1表示区间内全部用到，0表示区间内有没用到的。
LL dp[505][505];
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
int main(){
    int t; cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>key[i];
        for(int i=1;i<=n;i++)
            cin>>val[i];
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<n;i++){
            if(gcd(key[i],key[i+1])!=1){
                dp[i][i+1]=val[i]+val[i+1];
                vis[i][i+1]=1;
            }
        }
        for(int l=3;l<=n;l++)
        for(int i=1;i<=n-l+1;i++){
            int j=i+l-1;
            for(int k=i;k<j;k++){
                if(vis[i][k]&&vis[k+1][j])
                    vis[i][j]=1;
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
            if(vis[i+1][j-1]&&gcd(key[i],key[j])!=1){
                vis[i][j]=1;
                dp[i][j]=dp[i+1][j-1]+val[i]+val[j];
            }
        }
        cout<<dp[1][n]<<endl;
    }

    return 0;
}

其实和我的那个写法差不多，，只不过判断i+1 j-1的方法不太一样，，我是维护了一个前缀和，，他是用vis标记搞的。