首先维护一个前缀和。 然后如果gcd(key[l], key[r]) != 1， 如果l == r-1， 那么dp[l][r] = val[l]+val[r]。 如果不相邻， 那么如果dp[l+1][r-1] 和pre[r-1][l]相等， 说明中间的那一段拿完了， 这种情况也可以将l和r取到。 剩下的就是普通的区间dp。
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <complex> #include <cmath> #include <map> #include <set> #include <string> #include <queue> #include <stack> #include <bitset> using namespace std; #define pb(x) push_back(x) #define ll long long #define mk(x, y) make_pair(x, y) #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<1|1 #define mem1(a) memset(a, -1, sizeof(a)) #define mem2(a) memset(a, 0x3f, sizeof(a)) #define rep(i, n, a) for(int i = a; i<n; i++) #define fi first #define se second typedef complex <double> cmx; typedef pair<int, int> pll; const double PI = acos(-1.0); const double eps = 1e-8; const int mod = 1e9+7; const int inf = 1061109567; const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; const int maxn = 305; int key[maxn], val[maxn]; ll pre[maxn], dp[maxn][maxn]; ll dfs(int l, int r) { if(~dp[l][r]) return dp[l][r]; if(l >= r) return dp[l][r] = 0; if(l == r - 1) { if(__gcd(key[l], key[r]) != 1) { return dp[l][r] = val[l] + val[r]; } return dp[l][r] = 0; } dp[l][r] = 0; for(int i = l; i < r; i++) { dp[l][r] = max(dp[l][r], dfs(l, i) + dfs(i+1, r)); } if(__gcd(key[l], key[r]) != 1 && r - l > 2 && dp[l+1][r-1] == pre[r-1]-pre[l]) { dp[l][r] = max(dp[l][r], pre[r] - pre[l-1]); } return dp[l][r]; } int main() { int t, n; cin>>t; while(t--) { cin>>n; mem1(dp); for(int i = 1; i <= n; i++) { scanf("%d", &key[i]); } for(int i = 1; i <= n; i++) { scanf("%d", &val[i]); pre[i] = pre[i-1] + val[i]; } cout << dfs(1, n) << endl; } return 0; }