题意：给你n对pair 里面有两个值，分别是key 和 val 。你可以取相邻的两个pair 获得其中的val，前提是两个pair 的key 的 gcd 不为 1。当然你把相邻的两个取走了之后原本不相邻的两个就变得相邻了。比如：你将下标为 2，3 取走之后，下标1,4就变得相邻了，求你可以获得的最大val。
题解：典型的合并问题，应该能想到用区间dp，但这里得考虑清楚，状态怎么转移。我们定义dp[i][j]为i~j能够获取的最大值。那么怎么更新状态呢，我们用一个前缀和去维护val，如果
dp[i+1][j-1]能够取完，其值一定为sum[j-1]-sum[i]。如果当前的区间i,j互质，那么i~j都可以取完。否则我们就要考虑剩下哪些val能够使最终的结果最大，这里就用for循环去跑一遍，枚举中间值k,看剩下哪些值是最优解。
（对区间dp的构造有了更深的理解 过几天可以写一篇小结了）。
ac代码：
#include <cstdio> #include <iostream> #include <cstring> #define mt(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; ll key[302]; ll v[302]; ll dp[303][303]; ll sum[303]; ll gcd(ll a,ll b) { if(b==0) return a; return gcd(b,a%b); } int main() { int t; scanf("%d",&t); while(t--) { int n; mt(dp); mt(sum); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",&key[i]); } for(int i=1;i<=n;i++) { scanf("%lld",&v[i]); sum[i]=sum[i-1]+v[i]; } for(int l=2;l<=n;l++) { for(int i=1;i+l-1<=n;i++) { int j=i+l-1; if(dp[i+1][j-1]==(sum[j-1]-sum[i]) && gcd(key[i],key[j])!=1) { dp[i][j]=sum[j]-sum[i-1]; continue; } 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]); } }