优秀简历制作网站,中企动力邮箱登陆入口,建设网站技术公司,如何在国际上做网站283. 多边形 - AcWing题库
“多边形游戏”是一款单人益智游戏。
游戏开始时#xff0c;给定玩家一个具有 N 个顶点 N 条边#xff08;编号 1∼N#xff09;的多边形#xff0c;如图 1 所示#xff0c;其中 N4
每个顶点上写有一个整数#xff0c;每个边上标有一个运算符…283. 多边形 - AcWing题库
“多边形游戏”是一款单人益智游戏。
游戏开始时给定玩家一个具有 N 个顶点 N 条边编号 1∼N的多边形如图 1 所示其中 N4
每个顶点上写有一个整数每个边上标有一个运算符 加号或运算符 *乘号。 第一步玩家选择一条边将它删除。
接下来在进行 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
解析 简单题注意细节
#includeiostream
#includecstdio
#includecstdlib
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemap
using namespace std;
typedef long long LL;
const int N 110,INF1e8;
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], maxlmaxr);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;
}
