ZOJ Monthly, July 2010解题报告 » ZOJ3352

ZOJ3352
ZOJ3352.cpp


#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
12 Responses to “ZOJ3352”
  1. zt says:

    分析了楼主的代码才发现我题意彻底理解错了,一直以为是每人一面旗,移动自己的小旗……

  2. R says:

    请教前辈,我认为若两面旗的位置以及当前轮到谁走都确定,则对于这个局面对应的最优解就确定了,为什么搜索时要把当前赌资多少考虑进去呢?某人表示理解不能= =
    凡是有关DP的,DP数组的几个下标我都不太会选,经常碰运气,选错了DP就全错了,前辈有什么好方法介绍一下?
    感谢~

    • watashi says:

      要保证“最优子问题“和“无后效性“,选错DP状态表示,可能就做不到无后效性的
      因为最后结果和赌资有关,所以光以两面旗的位置和谁走做状态可能不够,我也曾想过以两面旗的位置和最终胜负做状态

      • R says:

        试考虑:b[x0][y0][10]=12与b[x0][y0][9]=11不是一回事吗?因为通过后面的博弈都让你多挣了2元。

        • watashi says:

          不一样的。因为你不知道你是输了还是赢了,这个要取相反数,就不一样了
          所以我考虑过以两面旗的位置和最终胜负做状态,没仔细想,不确定

          • xjdx says:

            我的DP就是这么写的 不知道楼主是否有数据..我拿我们程序测测看 我就知道这种DP存在什么问题了
            如果按位置和胜负状态DP的话我光方程就写了6个 也不知道对不对…

  3. skydream says:

    你太牛了。 哪天我才能像你一样啊。我想问的是你写程序多长时间了啊。

  4. xjdx says:

    您这题是用递归写的 写的非常漂亮 免去了拓扑和一些边界的判断
    我想请教的是 对于这种类型的题目如何判断其递归的时候不会栈溢出呢 请介绍下您的经验吧
    thanks

    • watashi says:

      这题最多递归MAXN+MAXN层就不能移动了,这个很少的,不可能栈溢出的
      如果栈有4M大小的话,这个函数至少能递归个10w数量级层

  5. haoren says:

    还是不大明白,对每个状态求最大值,但如果L输了,那不是意味着他要付出更多的钱吗?

    • xjdx says:

      整数比负数大
      for (vector::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;
      }
      “if (tmp > ret)”

  6.  
Leave a Reply