程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4597 Play Game(記憶化搜索)

hdu 4597 Play Game(記憶化搜索)

編輯:C++入門知識

題目鏈接:hdu 4597 Play Game


題目大意:給出兩堆牌,只能從最上和最下取,然後兩個人輪流取,都按照自己最優的策略,問說第一個人對多的分值。


解題思路:記憶化搜索,狀態出來就非常水,dp[fl][fr][sl][sr][flag],表示第一堆牌上邊取到fl,下面取到fr,同樣sl,sr為第二堆牌,flag為第幾個人在取。如果是第一個人,dp既要盡量大,如果是第二個人,那麼肯定盡量小。


#include 
#include 
#include 

using namespace std;

const int N = 25;
const int INF = 0x3f3f3f3f;
int n, f[N], s[N], dp[N][N][N][N][2];

void init () {
	memset(dp, -1, sizeof(dp));

	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &f[i]);
	for (int i = 1; i <= n; i++)
		scanf("%d", &s[i]);
}

int solve (int fl, int fr, int sl, int sr, int flag) {
	int& ans = dp[fl][fr][sl][sr][flag];
	if (fl > fr && sl > sr)
		return ans = 0;

	if (ans != -1)
		return ans;

	if (flag) {
		ans = 0;
		if (fl <= fr) {
			ans = max(ans, solve(fl+1, fr, sl, sr, 1-flag) + f[fl]);
			ans = max(ans, solve(fl, fr-1, sl, sr, 1-flag) + f[fr]);
		}

		if (sl <= sr) {
			ans = max(ans, solve(fl, fr, sl+1, sr, 1-flag) + s[sl]);
			ans = max(ans, solve(fl, fr, sl, sr-1, 1-flag) + s[sr]);
		}
	} else {
		ans = INF;
		if (fl <= fr) {
			ans = min(ans, solve(fl+1, fr, sl, sr, 1-flag));
			ans = min(ans, solve(fl, fr-1, sl, sr, 1-flag));
		}

		if (sl <= sr) {
			ans = min(ans, solve(fl, fr, sl+1, sr, 1-flag));
			ans = min(ans, solve(fl, fr, sl, sr-1, 1-flag));
		}
	}
	return ans;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init ();
		printf("%d\n", solve(1, n, 1, n, 1));
	}
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved