題目大意：

有n對二元組(key, value)，兩個相鄰的元組間如果key的不互質，那么可以被移除，并獲得兩個元組的value值之和的分數，問你最多能有多少分數。

解題思路：

區間DP

按照最裸的區間DP模型用記憶化搜索寫是要超時的...

本題的模型可以參考POJ-2955 Brackets題解這里有~

設dp[i][j]表示區間[i, j]能獲得的最大分數狀態轉移就可以寫成

dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j], dp[i+1][j-1] + value[i] + value[j]);

剩下的就很簡單了。

代碼：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std;typedef long long LL; const int maxn = 305;bool judge[maxn][maxn]; pair<int, int> p[maxn]; LL sum[maxn], dp[maxn][maxn];LL gcd(LL a, LL b) {while (b) {LL tmp = a % b;a = b;b = tmp;}return a; }int main() {int n, t;scanf("%d", &t);while (t--) {scanf("%d", &n);sum[0] = 0;for (int i = 1; i <= n; ++i)scanf("%d", &p[i].first);for (int i = 1; i <= n; ++i) {scanf("%d", &p[i].second);sum[i] = sum[i - 1] + p[i].second;}memset(judge, false, sizeof(judge));for (int i = 1; i <= n; ++i) {for (int j = i + 1; j <= n; ++j)judge[i][j] = (gcd(p[i].first, p[j].first) == 1 ? false : true);}for (int i = n; i >= 1; --i) {for (int j = i; j <= n; ++j) {dp[i][j] = 0;for (int k = i; k < j; ++k)dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);if ((i + 1 == j || dp[i + 1][j - 1] == sum[j - 1] - sum[i]) && judge[i][j])dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + p[i].second + p[j].second);}}printf("%lld\n", dp[1][n]);}return 0; }

轉載于:https://www.cnblogs.com/wiklvrain/p/8179353.html

總結

以上是生活随笔為你收集整理的HDU-5900 QSC and Master的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。