POJ1179 Polygon 区间DP

题目大意：

多边形游戏，有N个顶点的多边形，3 <= N <= 50 ，多边形有N条边，每个顶点中有一个数字（可正可负），每条边上或者是“+”号，或者是“*”号。边从1到N编号，首先选择一条边移去，然后进行如下操作：

1 选择一条边E和边E连接着的两个顶点V1，V2。

2 用一个新的顶点代替边E和V1、V2，新顶点的值为V1、V2中的值进行边上代表的操作得来（相加或相乘）

当最后只剩一个顶点，没有边时，游戏结束。现在的任务是编程求出最后的顶点能获得的最大值，以及输出取该最大值时，第一步需移去的边，如果有多条符合条件的边，按编号从小到大输出。

拆掉一条边后原环就形成了一条链，定义DP[l][r][0]为把顶点l,r合并后的最小值（意义在于相乘时负负得正的情况），DP[l][r][1]为最大值，则递归式为：

对于每个mid∈[l,r)，

                if (e == '+')

                {

                    DP[l][r][] = max(DP[l][r][], DP[l][mid][] + DP[mid + ][r][]);

                    DP[l][r][] = min(DP[l][r][], DP[l][mid][] + DP[mid + ][r][]);

                }

                else if (e == '*')

                {

                    DP[l][r][] = max(DP[l][r][], DP[l][mid][] * DP[mid + ][r][]);

                    DP[l][r][] = max(DP[l][r][], DP[l][mid][] * DP[mid + ][r][]);

                    DP[l][r][] = min(DP[l][r][], DP[l][mid][] * DP[mid + ][r][]);

                    DP[l][r][] = min(DP[l][r][], DP[l][mid][] * DP[mid + ][r][]);

                    DP[l][r][] = min(DP[l][r][], DP[l][mid][] * DP[mid + ][r][]);

                }
//e指边的符号

一个一个拆边有些太慢，我们可以如此操作：将环复制成两份，第一份边1删去，第二份边N删去，将第一份点N与第二份边1相连，这样所有可能的链的情况便在这条大链中表示出来了。

代码如下（注意循环终止条件）：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdarg>

using namespace std;

const int MAX_N = 110, INF = 0x3f3f3f3f;

int P[MAX_N], DP[MAX_N][MAX_N][2], Cut[MAX_N], AnsCnt, N;

char E[MAX_N];

int Proceed()

{

	for (int i = 1; i <= N * 2; i++)

	{

		for (int j = 1; j <= N * 2; j++)

		{

			DP[i][j][0] = INF;

			DP[i][j][1] = -INF;

		}

	}

	for (int i = 1; i <= N; i++)

		DP[i][i][0] = DP[i][i][1] = DP[i + N][i + N][0] = DP[i + N][i + N][1] = P[i];

	for (int len = 1; len < N; len++)//注意是小于，不是小于等于

	{

		for (int l = 1; l < N * 2 - len; l++)//小于，不是小于等于

		{

			int r = l + len;

			for (int mid = l; mid < r; mid++)

			{

				char e = E[mid + 1];

				if (e == '+')

				{

					DP[l][r][1] = max(DP[l][r][1], DP[l][mid][1] + DP[mid + 1][r][1]);

					DP[l][r][0] = min(DP[l][r][0], DP[l][mid][0] + DP[mid + 1][r][0]);

				}

				else if (e == '*')

				{

					DP[l][r][1] = max(DP[l][r][1], DP[l][mid][1] * DP[mid + 1][r][1]);

					DP[l][r][1] = max(DP[l][r][1], DP[l][mid][0] * DP[mid + 1][r][0]);

					DP[l][r][0] = min(DP[l][r][0], DP[l][mid][0] * DP[mid + 1][r][0]);

					DP[l][r][0] = min(DP[l][r][0], DP[l][mid][0] * DP[mid + 1][r][1]);

					DP[l][r][0] = min(DP[l][r][0], DP[l][mid][1] * DP[mid + 1][r][0]);

				}

			}

		}

	}

	AnsCnt = 0;

	int ans = -INF;

	for (int l = 1; l <= N; l++)

	{

		int r = l + N - 1;

		if (DP[l][r][1] > ans)

		{

			ans = DP[l][r][1];

			Cut[AnsCnt = 1] = l;

		}

		else if (DP[l][r][1] == ans)

			Cut[++AnsCnt] = l;

	}

	return ans;

}

int main()

{

#ifdef _DEBUG

	freopen("c:\\noi\\source\\input.txt", "r", stdin);

#endif

	int x;

	char c;

	scanf("%d\n", &N);

	for (int i = 1; i <= N; i++)

	{

		scanf("%c %d ", &c, &x);

		P[i] = P[i + N] = x;

		E[i] = E[i + N] = c == 't' ? '+' : '*';

	}

	printf("%d\n", Proceed());

	for (int i = 1; i <= AnsCnt; i++)

		printf("%d ", Cut[i]);

	printf("\n");

	return 0;

}

巴特西

POJ1179 Polygon 区间DP

最新文章

热门文章