首页 > 代码库 > HDU 5900 QSC and Master （区间DP）
HDU 5900 QSC and Master （区间DP）
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5900
题意：给出序列Ai.key和Ai.value，若当前相邻的两个数Ai.key和Ai+1.key的最大公约数大于1，则可以把这两个数消去，同时消去Ai.value和Ai+1.value，每次消去得到的分数为Ai和Ai+1的value值，问最大可能得分。
注意：当Ai和Ai+1被消去后，Ai-1和Ai+2成为了新的相邻的数。若符合条件则可以继续消去。
思路：很明显是区间DP，但是我比赛中如何也A不了。原因有两个：1.没有注意到位运算的低优先级。2.没有把所有情况考虑清楚。
设f[i][j]为从第i个数到第j个数所能得到的最大得分，j-i+1从2开始依次枚举，最后枚举到f[1][n]（考虑DP的无后效性）
分类讨论即可。先考虑不合并的情况，则f[i][j]被f[i][k]+f[k + 1][j]依次更新。
再考虑合并的情况f[i][j]可以被f[i][k] + a[k + 1] + a[k + 2] + f[k +3][j]更新。
特殊情况讨论：当a[i + 1]到a[j - 1]中所有的数都可以被消去，则a[i]和a[j]作为相邻的数也可以被消去。这种情况的讨论非常重要！！！
代码送上
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <functional> 6 7 using namespace std; 8 9 #define REP(i,n) for(int i(0); i < (n); ++i)10 #define rep(i,a,b) for(int i(a); i <= (b); ++i)11 #define dec(i,a,b) for(int i(a); i >= (b); --i)12 #define for_edge(i,x) for(int i = H[x]; i; i = X[i])13 14 const int N = 100000 + 10;15 const int M = 10000 + 10;16 const int Q = 1000 + 10;17 const int A = 30 + 1;18 19 typedef long long LL;20 21 LL f[Q][Q];22 bool c[Q][Q];23 bool ret[Q][Q];24 int T;25 int n;26 LL a[Q], b[Q];27 LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a % b); }28 29 30 int main(){31 scanf("%d", &T);32 while (T--){33 scanf("%d", &n);34 memset(a, 0, sizeof a);35 memset(b, 0, sizeof b);36 memset(c, false, sizeof c);37 memset(ret, false, sizeof ret);38 memset(f, 0, sizeof f);39 rep(i, 1, n) scanf("%lld", a + i);40 rep(i, 1, n) scanf("%lld", b + i);41 rep(i, 1, n - 1) rep(j, i + 1, n) if (gcd(a[i], a[j]) != 1) c[i][j] = true;42 rep(i, 1, n - 1) if (gcd(a[i], a[i + 1]) > 1) ret[i][i + 1] = true;43 for (int len = 4; len <= n; len += 2){44 rep(i, 1, n - len + 1){45 int j = i + len - 1;46 bool flag = false;47 if (c[i][i + 1] && ret[i + 2][j]) flag = true;48 if (c[j - 1][j] && ret[i][j - 2]) flag = true;49 if (c[i][j] && ret[i + 1][j - 1]) flag = true;50 for (int k = i + 2; k <= j - 3; k += 2) if (ret[k][k + 1] && ret[i][k - 1] && ret[k + 2][j]){ flag = true; break;}51 if (flag) ret[i][j] = true;52 }53 }54 55 rep(i, 1, n - 1) if (c[i][i + 1]) f[i][i + 1] = b[i] + b[i + 1];56 rep(i, 1, n - 2) f[i][i + 2] = max(f[i][i + 1], f[i + 1][i + 2]);57 rep(len, 4, n){58 rep(i, 1, n - len + 1){59 int j = i + len - 1;60 rep(k, i, j) f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);61 if (len % 2 == 0){ if (ret[i + 1][j - 1] && c[i][j]) f[i][j] = max(f[i][j], b[i] + b[j] + f[i + 1][j - 1]); }62 f[i][j] = max(f[i][j], f[i + 1][j]);63 f[i][j] = max(f[i][j], f[i][j - 1]);64 if (c[i][i + 1]) f[i][j] = max(f[i][i + 1] + f[i + 2][j], f[i][j]);65 if (c[j - 1][j]) f[i][j] = max(f[j - 1][j] + f[i][j - 2], f[i][j]);66 rep(k, i + 1, j - 2) if (c[k][k + 1]) f[i][j] = max(f[i][j], f[i][k - 1] + f[k][k + 1] + f[k + 2][j]);67 }68 }69 printf("%lld\n", f[1][n]);70 71 72 }73 74 75 return 0;76 77 }
HDU 5900 QSC and Master （区间DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。