给定 n n 个二元组，每个二元组由键和值构成，当且仅当相邻的两个二元组的键互质的时候，它们可以被消去，这时得到的价值为它们值的和，然后两边的元素链接在一起。

求能够获得的最大价值。

题解

两遍 dp ，第一遍处理出某个区间 [l, r] 中的 value 能否被全部得到，方法如下: 

let canEarnAll(l, r) equal to if all the value in [l, r] can be earned;
canEarnAll(l, r) |= (canEarnAll(l + 1, r - 1) & (gcd(l, r) != 1));
for (int k = l; k < r; k++) canEarnAll |= (canEarnAll(l, k) & canEarnAll(k + 1, r));

然后按照做出来的结果继续 dp，方法如下: 

let maxValue equal to the max value can be earned in [l, r];
if (canEarnAll(l, r) == true) maxValue(l, r) = sumValue(l, r);
else for (int k = l; k < r; k++) maxValue(l, r) = max(maxValue(l, r), maxValue(l, k) + maxValue(k + 1, r));

最后 maxValue(1, n) 即为答案。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
const int MAXN = 500;
long long f[MAXN + 1][MAXN + 1], key[MAXN + 1], val[MAXN + 1], ans = 0;
bool canEarnAll[MAXN + 1][MAXN + 1];
int n;
long long gcd(long long a, long long b) {
    return !b ? a : gcd(b, a % b);
}
int main() {
    int T_T;
    scanf("%d", &T_T);
    for (int i = 1; i <= T_T; i++) {
        memset(f, 0, sizeof(f));
        memset(canEarnAll, 0, sizeof(canEarnAll));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%lld", &key[i]);
        for (int i = 1; i <= n; i++) scanf("%lld", &val[i]), val[i] += val[i - 1], canEarnAll[i][i - 1] = true;
        canEarnAll[n + 1][n] = true;
        
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                    canEarnAll[i][j] |= canEarnAll[i + 1][j - 1] & (gcd(key[i], key[j]) != 1);
                    if (!canEarnAll[i][j]) for (int k = i; k < j; k++) canEarnAll[i][j] |= canEarnAll[i][k] & canEarnAll[k + 1][j];
            }
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                if (canEarnAll[i][j]) f[i][j] = val[j] - val[i - 1];
                else for (int k = i; k < j; k++) f[i][j] = std::max(f[i][j], f[i][k] + f[k + 1][j]);
            }
        }
        printf("%lld\n", f[1][n]);
    }
    return 0;
}