题目链接：传送门
题目大意：长度为n的key数组与value数组，若相邻的key互斥，则可以删去这两个数同时获得对应的两
个value值，问最多能获得多少
题目思路：区间DP
闲谈： 这个题一开始没有做出来，找了下原因，是自己思维太局限（刷题太少），始终想怎样去维护相
邻这个条件，删去数之后怎么来拼接左右两段。。。最后导致没解出来。。
正解： 其实维护拼接我们可以用一个数组来实现，先预处理原数组中相邻的两个数，然后再利用区间
DP思想来进行扩展，最后根据这个预处理好的数组来实现判断与更新。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 1000050 #define maxn 3001 typedef pair<int,int> PII; typedef long long LL; int n,m; int key[500],va[500]; LL sum[500]; int ok[500][500]; LL dp[500][500]; LL ans; LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } void init(){ mst(ok,0); for(int i=2;i<=n;++i)ok[i-1][i]=__gcd(key[i],key[i-1])==1?0:1; for(int l=3;l<=n;++l) for(int i=1;i+l-1<=n;++i){ int j=i+l-1; ok[i][j]=(ok[i+1][j-1]&&__gcd(key[i],key[j])!=1); for(int k=i;k<j;++k) ok[i][j]+=(ok[i][k]&&ok[k+1][j]); } } void solve(){ mst(dp,0); for(int l=2;l<=n;++l) for(int i=1;i+l-1<=n;++i){ int j=i+l-1; if(ok[i][j]) dp[i][j]=sum[j]-sum[i-1]; else{ for(int k=i;k<j;++k){ dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]); } } } printf("%lld ",dp[1][n]); } int main(){ int i,j,group; group=read(); while(group--){ scanf("%d",&n); for(i=1;i<=n;++i) key[i]=read(); for(j=1;j<=n;++j) va[j]=read(),sum[j]=sum[j-1]+va[j]; init(); solve(); } return 0; }