283. 多边形,《算法竞赛进阶指南》,

283. 多边形 - AcWing题库

“多边形游戏”是一款单人益智游戏。

游戏开始时，给定玩家一个具有 N 个顶点 N 条边（编号 1∼N）的多边形，如图 1 所示，其中 N=4

每个顶点上写有一个整数，每个边上标有一个运算符 +（加号）或运算符 *（乘号）。

第一步，玩家选择一条边，将它删除。

接下来在进行 N−1 步，在每一步中，玩家选择一条边，把这条边以及该边连接的两个顶点用一个新的顶点代替，新顶点上的整数值等于删去的两个顶点上的数按照删去的边上标有的符号进行计算得到的结果。

下面是用图 1 给出的四边形进行游戏的全过程。

最终，游戏仅剩一个顶点，顶点上的数值就是玩家的得分，上图玩家得分为 0。

请计算对于给定的 N 边形，玩家最高能获得多少分，以及第一步有哪些策略可以使玩家获得最高得分。

输入格式

输入包含两行，第一行为整数 N。

第二行用来描述多边形所有边上的符号以及所有顶点上的整数，从编号为 1 的边开始，边、点、边…按顺序描述。

其中描述顶点即为输入顶点上的整数，描述边即为输入边上的符号，其中加号用 t 表示，乘号用 x 表示。

输出格式

输出包含两行，第一行输出最高分数。

在第二行，将满足得到最高分数的情况下，所有的可以在第一步删除的边的编号从小到大输出，数据之间用空格隔开。

数据范围

3≤N≤50
数据保证无论玩家如何操作，顶点上的数值均在 [−32768,32767]之内。

输入样例：

4
t -7 t 4 x 2 x 5

输出样例：

33
1 2

解析：
简单题，注意细节

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 110,INF=1e8;
int n;
char c[N];
int a[N];
int f[N][N], g[N][N];
 
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> c[i] >> a[i];
		a[i + n] = a[i];
		c[i + n] = c[i];
	}
	for (int len = 1; len <= n; len++) {
		for (int i = 1; i + len - 1 <= 2 * n; i++) {
			int j = i + len - 1;
			if (len == 1) {
				f[i][j] = a[i];
				g[i][j] = a[i];
			}
			else {
				
				f[i][j] = -INF, g[i][j] = INF;
				for (int k = i; k < j; k++) {
					int minl = g[i][k], minr = g[k + 1][j], maxl = f[i][k], maxr = f[k + 1][j];
					if (c[k + 1] == 't') {
						f[i][j] = max(f[i][j], maxl+maxr);
						g[i][j] = min(g[i][j], minl + minr);
					}
					else {
						
						int x1 = minl * minr, x2 = minl * maxr, x3 = maxl * minr, x4 = maxl * maxr;
						f[i][j] = max(f[i][j], max(max(x1, x2), max(x3, x4)));
						g[i][j] = min(g[i][j], min(min(x1, x2), min(x3, x4)));
					}
				}
			}
		}
	}
	int ans = -INF;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, f[i][i + n - 1]);
	}
	cout << ans << endl;
	for (int i = 1; i <= n; i++) {
		if (ans == f[i][i + n - 1]) {
			cout << i << " ";
		}
	}
	cout << endl;
	return 0;
}