sdnu 1261.Problem J. Alice and Bob II 巧妙地dfs+dp用法；

141 2 3 4

Case #1:  6

            这道题~大体意思就是Alice和一个人分别拿石子~~每次每人可以从两端中的一选一堆拿走~双方都绝顶聪明~~在Alice先手的情况下，Alice最多能拿到多少堆；

            这道题要用dp来创造一个辅助数组dp，dp[l][r]表示在在剩下的l到r堆石子的情况下~Alice能拿到的最多的石子数量。

            然后就用dfs进行深度优先搜索~~，l，r表示现在的剩下的石子堆数情况~cnt用来看现在是谁要动手了~~

            假如现在是Alice开始了(cnt%2==1)~~那么一共就是两种情况：从左边开始拿~再加上剩下的区间他能拿到的最大值；；再就是从右边开始拿~再加上左边区间他能拿到的最大值----------但是如果现在是对手的回合(cnt)~~那就不一样了~~

对手会有两个选择：：拿左边的，让A拿右边的：：拿右边的，让A拿左边的~~但是最后~~他会让A拿到区间值最小的。dfs的最后就是当l===r的时候~~看现在谁的回合来判定~~

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int m[105];
int dp[105][105];
int ans;
int dfs(int l, int r, int cnt)
{
	//cout << l << " " << r << endl;
	if (l == r)
	{
		if (cnt % 2)
		{
			return m[l];
		}
		else
		{
			return 0;
		}
	}
	if (dp[l][r] != 0)
	{
		return dp[l][r];
	}
	else
	{
		int e;
		e = cnt % 2 == 1 ? 1 : 0;
		if (e)
		{
			int a1 = 0;
			a1 += m[l] + dfs(l + 1, r, cnt + 1);
			int a2 = 0;
			a2 += m[r] + dfs(l, r - 1, cnt + 1);
			dp[l][r] = a1 > a2 ? a1 : a2;
			return dp[l][r];
		}
		else
		{
			int a1 = 0;
			a1 = dfs(l + 1, r, cnt + 1);
			int a2 = 0;
			a2 = dfs(l, r - 1, cnt + 1);
			dp[l][r] = a1 < a2 ? a1 : a2;
		//	cout << l << " " << r << " " << dp[l][r] << endl;
			return dp[l][r];
		}
	}
}
int main()
{
	int te;
	scanf("%d", &te);
	int t = 1;
	while (te--)
	{	
		int n;
		scanf("%d", &n);
		memset(dp, 0, sizeof(dp));
		ans = 0;
		for (int s = 1; s <= n; s++)
		{
			scanf("%d", &m[s]);
		}
		for (int s = 1; s <= n; s++)
		{
			dp[s][s] = m[s];
		}
		printf("Case #%d: %d\n", t++, dfs(1, n, 1));
	}
	return 0;
}