首页 > 代码库 > HDU 5900 - QSC and Master [ DP ]
HDU 5900 - QSC and Master [ DP ]
题意：
给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 }
HDU 5900 - QSC and Master [ DP ]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。