題目鏈接：http://vjudge.net/problem/viewProblem.action?id=19461

思路：一類經典的博弈類區間dp,我們令dp[l][r]表示玩家A從區間[l, r]得到的最大值，于是就有dp[l][r] = sum[l][r] - min(dp[l + i][r], dp[l][r - i]) (i >= 1 && i + l <= r),最終我們要求的就是dp[1][n] - (sum[1][n] - dp[1][n]).

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <climits> #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) #define RFOR(i, a, b) for (int i = (a); i >= (b); --i) using namespace std;int dp[111][111], sum[111], a[111], N;int dfs(int l, int r) {if (l > r) return 0;if (~dp[l][r]) return dp[l][r];int res = 0;FOR(i, l + 1, r) {res = min(res, dfs(i, r));}RFOR(i, r - 1, l) {res = min(res, dfs(l, i));}return dp[l][r] = sum[r] - sum[l - 1] - res; }int main() {while (cin >> N && N) {FOR(i, 1, N) cin >> a[i], sum[i] = sum[i - 1] + a[i];memset(dp, -1, sizeof(dp));cout << 2 * dfs(1, N) - sum[N] << endl;}return 0; }

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4597

這道題和上一題差不多，只是多了維數，dp[al][ar][bl][br]表示從第一堆的al~ar和第二堆的bl~br中取得的最大值.

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) using namespace std;int a[22], b[22], N; int dp[22][22][22][22];int dfs(int al, int ar, int bl, int br, int sum) {if (al > ar && bl > br) return 0;if (~dp[al][ar][bl][br]) return dp[al][ar][bl][br];int res = 0;if (al <= ar) {res = max(res, sum - dfs(al + 1, ar, bl, br, sum - a[al]));res = max(res, sum - dfs(al, ar - 1, bl, br, sum - a[ar]));}if (bl <= br) {res = max(res, sum - dfs(al, ar, bl + 1, br, sum - b[bl]));res = max(res, sum - dfs(al, ar, bl, br - 1, sum - b[br]));}return dp[al][ar][bl][br] = res; }int main() {int Cas; cin >> Cas;while (Cas--) {cin >> N; int sum = 0;FOR(i, 1, N) cin >> a[i], sum += a[i];FOR(i, 1, N) cin >> b[i], sum += b[i];memset(dp, -1, sizeof(dp));cout << dfs(1, N, 1, N, sum) << endl;}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4597 + uva 10891(一类区间dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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