題意:
給n件物品,有key和value
每次可以把相鄰的 GCD(key[i], key[i+1]) != 1 的兩件物品,問移除的物品的總value最多是多少
key : 1 3 4 2 移除34以後12也相鄰了,可以移除
分析:
先預處理出所有GCD[l][r], 意味 l <= i <= r的區域可以全部移除, 用記憶化搜尋處理
然後 dp[i] 代表到 i 為止可以得到的最大value和
if (G[l][r]) dp[r] = max(dp[r], dp[l-1] + sum[r] - sum[l-1] )
以及用 dp[i] = max(dp[i], dp[i-1]) 向後保留最大值
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 #define LL long long
6 const int MAXN = 305;
7 int t, n;
8 LL dp[MAXN];
9 LL key[MAXN], v[MAXN], sum[MAXN];
10 int GCD[MAXN][MAXN];
11 LL gcd(LL a, LL b)
12 {
13 return b == 0 ? a : gcd(b, a%b);
14 }
15 bool check(int l, int r)
16 {
17 if (l > r) return 1;
18 if (GCD[l][r] != -1) return GCD[l][r];
19 if (l == r) return GCD[l][r] = 0;
20 if ((r-l)%2 == 0) return GCD[l][r] = 0;
21 if (l == r-1) return GCD[l][r] = ( gcd(key[l], key[r]) != 1 );
22 if (gcd(key[l], key[r]) != 1 && check(l+1, r-1) ) return GCD[l][r] = 1;
23 for (int i = l+1; i < r-1; i++)
24 {
25 if (check(l,i) && check(i+1, r)) return GCD[l][r] = 1;
26 }
27 return GCD[l][r] = 0;
28 }
29 int main()
30 {
31 scanf("%d", &t);
32 while (t--)
33 {
34 scanf("%d", &n);
35 for (int i = 1; i <= n; i++)
36 scanf("%lld", &key[i]);
37 sum[0] = 0;
38 for (int i = 1; i <= n; i++)
39 scanf("%lld", &v[i]) , sum[i] = sum[i-1] + v[i];
40 memset(GCD, -1, sizeof(GCD));
41 for (int i = 1; i <= n; i++)
42 for (int j = i; j <= n; j++)
43 check(i, j);
44 memset(dp, 0, sizeof(dp));
45 for (int i = 1; i <= n; i++)
46 {
47 for (int j = 2; j <= i; j += 2)
48 {
49 int l = i - j + 1, r = i;
50 if (check(l, r))
51 dp[i] = max(dp[i], dp[l-1] + sum[r] - sum[l-1]);
52 }
53 dp[i] = max(dp[i], dp[i-1]);
54 }
55 printf("%lld\n", dp[n]);
56 }
57 }
轉載于:https://www.cnblogs.com/nicetomeetu/p/5907060.html