题意

有一个序列，每个元素都有一个键值key，和一个价值value。假如其中相邻的两个元素的键值的最大公约数不为1（不互质），可以把这两个元素从序列中取走，并或得这两个元素价值的分数，可以一直取，问最大能或得多少分数。

思路

这是一道典型的区间dp，然而比赛的时候跟本没什么想法。。用dp[i][j]来表示区间[i,j]能获得的最大值。实际上对于区间[i,j]只有几种可能，首先对于一个大区间，我们很容易想到拆成小区间来解决。所以很明显用一个k来循环，dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j])，其次当 gcd(key[i],key[j])!=1 时，这时有两种情况： 1. j=i+1 ，在这种情况下，很显然dp[i][j] = value[i] + value[j]。 2. j!=i+1 ，这时只有当区间[i + 1, j - 1]中所有的数字都被取走了的时候，dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + value[i] + value[j]),这个条件可以通过判断dp[i + 1][j - 1]的值是否等于value[i + 1]~value[j - 1]的和来得到。

代码

#include <cstdio> #include <iostream> #include <cstring> #define ll long long using namespace std; const int kMaxn = 300 + 5; ll dp[kMaxn][kMaxn]; ll key[kMaxn]; ll value[kMaxn]; ll sum[kMaxn]; ll Gcd(ll a, ll b) { if(a % b == 0) return b; return Gcd(b, a % b); } int main() { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); sum[0] = 0; for(int i = 1; i <= n; i++) scanf("%lld", &key[i]); for(int i = 1; i <= n; i++) { scanf("%lld", &value[i]); sum[i] = sum[i - 1] + value[i]; } memset(dp, 0, sizeof(dp)); for(int len = 2; len <= n; len ++) { for(int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; for(int k = i; k < j; k++) dp[i][j] = max(dp[i][k] + dp[k + 1][j], dp[i][j]); if(Gcd(key[i], key[j]) != 1) if(j == i + 1) dp[i][j] = value[i] + value[j]; else if(dp[i + 1][j - 1] == sum[j - 1] - sum[i]) dp[i][j] = dp[i + 1][j - 1] + value[i] + value[j]; } } printf("%lld\n", dp[1][n]); } return 0; }