ZOJ3352【记忆化搜索】

先膜拜watashi！

前言：

比赛的时候，确定的是这是一个博弈，然后就是各种瞎猜，后面想到DP[ x ][ y ]代表x表白色的状态，y表黑色的状态，无果。挂机开始。GG、巨菜。

思路：

这一发记忆化搜索真是玄学。

仔细想想，首先我只要求权值最大，我不在乎输赢。

直接就是dp[i][j][k]代表当前白在 i 位置，黑在 j 位置，k为当前局势的赌资，dp存整个子结构包括本身的最大值。

然后记忆化搜索一发就可以了，很神奇。

记忆化搜索独有的味道：当前位置的状态为之前（其实是之后？）最优状态的转化（前身？）。

这里还有一点就是在搜的连续两步，其实分成了两个人的行为，所有当前的最大为之后那个人赢的相反数。（他赢即我输）

watashi美丽code:(小引用好酷)

#include <cstdio>

#include <vector>

#include <cstring>

using namespace std;

const int MAXN = 52;

const int INF = 65536;

int d[MAXN];

vector<int> e[MAXN];

int b[MAXN][MAXN][MAXN * 4];

int c[MAXN][MAXN][MAXN * 4];

int gao(int x, int y, int z) {

	if (c[x][y][100 + z] != -1) {

		return b[x][y][100 + z];

	}

	int tmp;

	int &ret = b[x][y][100 + z], &cnt = c[x][y][100 + z];

	ret = (e[x].empty() && e[y].empty()) ? -z : -INF;

	cnt = 1;

	for (vector<int>::const_iterator i = e[x].begin(); i != e[x].end(); ++i) {

		tmp = -gao(*i, y, z + d[*i]);

		if (tmp > ret) {

			ret = tmp;

			cnt = 1;

		} else if (tmp == ret) {

			++cnt;

		}

	}

	for (vector<int>::const_iterator i = e[y].begin(); i != e[y].end(); ++i) {

		tmp = -gao(x, *i, z - d[*i]);

		if (tmp > ret) {

			ret = tmp;

			cnt = 1;

		} else if (tmp == ret) {

			++cnt;

		}

	}

	return ret;

}

int main() {

	int n, m, x, y, s, t;

	while (scanf("%d%d%d%d", &n, &m, &x, &y) != EOF) {

		for (int i = 0; i < n; ++i) {

			scanf("%d", &d[i]);

			e[i].clear();

		}

		for (int i = 0; i < m; ++i) {

			scanf("%d%d", &s, &t);

			e[s].push_back(t);

		}

		memset(c, 0xff, sizeof(c));

		gao(x, y, 1);

		printf("%d %d\n", b[x][y][101], c[x][y][101]);

	}

	return 0;

}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin

//584 	2010-07-16 19:50:54 	Accepted 	1074 	C++ 	860 	4572 	anotherpeg 	Source

巴特西

ZOJ3352【记忆化搜索】

最新文章

热门文章