poj 1179 Polygon 多边形游戏 区间DP

缘起

继续做经典的DP问题. poj 1179 Polygon

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
多边形游戏，有N个顶点的多边形，3 <= N <= 50 ，多边形有N条边，每个顶点中有一个数字（可正可负），
每条边上或者是“+”号，或者是“*”号。边从1到N编号，首先选择一条边移去，然后进行如下操作：

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

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

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

【输入】
输入包含2行, 第一行是N. 第二行 t代表+, x代表* 号. 然后是整数. 整数的范围是  [-32768,32767]

【输出】
输出分成2行, 第一行输出最高分. 第二行输出为了达到该最大值, 第一步需要移掉的边, 如果有多条边符合的话
按照编号从小到大输出

【样例输入】
4
t -7 t 4 x 2 x 5

【样例输出】
33
1 2

【限制】
1s

【来源】
IOI 1998

此题是区间DP的一道好题~（不愧来自IOI）

上图给出了一种操作方案（但是可能不是最优的）. 该方案先选择了3这条边去除. 然后得到了一条链. 然后自由选择这条链上的运算. 最终得到结果.

首先, 你选择一条边断开导致原本的多边形（其实就是一个环）变成一条链可以这么刻画——选定一个端点,它逆时针走n个顶点（包括起点自己）构成的链. 例如上图, 选择3这条边断开, 则就是选定写着4的这个端点逆时针4个顶点（包括起点自己）.

所以我们就好进行区间DP了. 本题比较仁慈——只需要处理一组数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
令 m[i][j]是从顶点i顺时针走j个顶点（包括顶点i自己）形成的链能算出的最小值.
而M[i][j]是上述过程的最大值. 则最终答案就是M[1][n],...,M[n][n]中的最大值
(他们选择断掉的边是不一样的).
1<=i,j<=n
则dp方程是显然的（极具区间DP的风格~）, 令Pk是从i起步的k+1个顶点(包括i自己)到达的顶点
m[i][j]=
m[i][k]与m[Pk][j-k]运算(运算符是第k个顶点和第k+1个顶点之间的)
m[i][k]与M[Pk][j-k]运算(运算符是第k个顶点和第k+1个顶点之间的)
M[i][k]与m[Pk][j-k]运算(运算符是第k个顶点和第k+1个顶点之间的)
M[i][k]与M[Pk][j-k]运算(运算符是第k个顶点和第k+1个顶点之间的)
这四种运算中最小的（当然,也要遍历k）. 
这里插一句——明白了为什么题目只需要求最大的, 但是这里还是要把最小的给
DP出来了吧? 因为  (-2)*(-2)>1*3
这里吐槽一句~DP的题目其实挺难的~ 首先没有固定模式，只能靠做题积累感觉, 其次有的时候就算dp方程写出来了
也要涉及到dp方程的优化, 而且细节性的处理（例如初始值）一定要做好.

顺便说一句，我dp你老母~ dp细节太多~ 如果不卡空间的话, 记忆化搜索才是首选~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int inf = ~0u>>1;
int n, m[55][55], M[55][55], a[55],anse[55], top;
char op[55]; // 运算符 +或者 *
bool flagm[55][55], flagM[55][55]; // 用于记忆化搜索

void init() // 初始化 m和M
{
	for (int i = 1; i<=n;i++)
	{
		for (int j = 1; j<=n; j++)
		{
			m[i][j] = inf; // 最小值初始化
			M[i][j] = -inf; // 最大值初始化
		}
	}
	for (int i = 1; i<=n; i++)
	{
		m[i][1] = M[i][1] = a[i]; // 从i出发顺时针走1个顶点(包括i自己)就是i,则答案显然就是a[i]
		flagm[i][1] = flagM[i][1] = true;
	}
}

int nxt(int i, int j) // 顶点i(n>=i>=1)顺时针j(n>=j>=1)个顶点(包括它自己)后的顶点的标号
{
	return (i-1+j-1)%n+1; // 这么考虑这个问题——将所有顶点-1(i变成i-1),变成0~n-1, 然后就是(i-1+j-1)%n,  然后最后的结果要+1, 所以就是(i-1+j-1)%n+1啦~ 这和约瑟夫环的dp做法是一样的~
}

int nxtop(int i, int j) // 顶点i开始顺时针j个顶点后连接的那个符号
{
	return ((i-1+j-1)%n+1)%n+1;
}

int quaricm(int a, int b, int c, int d) // 求出[a,b]和[c,d]中做乘法能得到的最小数
{
	return min(a*c, b*d);
}

int quaricM(int a, int b, int c, int d) // 求出[a,b]和[c,d]中做乘法能得到的最大数
{
	return max(a*c, b*d);
}

int bwlm(int, int);
int bwlM(int, int);

int bwlm(int i, int j) // 记忆化搜索求m[i][j](我dp你个锤子~ dp细节太多, 伤不起~ n才50, 记忆化慢不到哪去)
{
	if (flagm[i][j])
	{
		return m[i][j];
	}
	int ans = inf;
	for (int k = 1; k<j; k++) // 枚举从顶点i顺时针走k个顶点, 然后切开
	{
		//[m[i][k],M[i][k]]和[m[nxt(i, k+1)][j-k],M[nxt(i, k+1)][j-k]]这两个区间之间搞出的最小值, 然后从顶点i出发顺时针走k个顶点后的那个符号是什么?
		char symb = nxtop(i,k); // 连接2个区间的符号
		int nxtvertex = nxt(i,k+1); // 分割后下一个链的起点
		if (op[symb]=='t') // 如果是加号, 则只能两个小的一起相加
		{
			ans = min(ans, bwlm(i, k) + bwlm(nxtvertex, j-k));
		}
		else // 如果是乘号的话
		{
			ans = min(ans, quaricm(bwlm(i,k), bwlM(i,k), bwlm(nxtvertex, j-k), bwlM(nxtvertex, j-k)));
		}
	}
	flagm[i][j] = true; // 记忆化
	return m[i][j] = ans;
}

int bwlM(int i, int j) // 记忆化搜索求M[i][j]
{
	if (flagM[i][j])
	{
		return M[i][j];
	}
	int ans = -inf;
	for (int k = 1; k<j; k++)
	{
		char symb = nxtop(i,k);
		int nxtvertex = nxt(i,k+1);
		if (op[symb]=='t') 
		{
			ans = max(ans, bwlM(i, k) + bwlM(nxtvertex, j-k));
		}
		else
		{
			ans = max(ans, quaricM(bwlm(i,k), bwlM(i,k), bwlm(nxtvertex, j-k), bwlM(nxtvertex, j-k)));
		}
	}
	flagM[i][j] = true;
	return M[i][j] = ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	getchar(); // 吸收多余换行符
	for (int i = 1; i<=n; i++)
	{
		scanf("%c", op+i);
		scanf("%d", a+i);
		getchar(); // 吸收多余空格
	}
	init(); // 初始化
	int ans = -inf;
	for (int i = 1;i<=n;i++)
	{
		ans = max(ans, bwlM(i,n));
	}
	printf("%d\n", ans);
	for (int i = 1; i<=n;i++)
	{
		if (bwlM(i,n)==ans)
		{
			anse[top++] = i;
		}
	}
	for (int i = 0; i<top; i++)
	{
		if (i)
		{
			putchar(' ');
		}
		printf("%d", anse[i]);
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 132kB
Length 2700
Lang C++
Submitted 2019-09-13 09:32:52
Shared
RemoteRunId 20857286