当前位置: 首页 > news >正文

13 ACwing 283 Polygon 题解

Polygon

题面

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

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

每个顶点上写有一个整数 \(a_i\) ,每个边上标有一个运算符 +(加号)或运算符 *(乘号)。

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

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

最终,游戏仅剩一个顶点,顶点上的数值就是玩家的得分

\(3 \le N \le 50\)

\(-32768 \le a_i \le 32768\)

题解

如果我们确定了先删哪条边,那么这道题就跟石子合并几乎一样了

环形问题的常见解决方法,可以断环为链,将原链复制一倍接在后面,然后正常做区间 dp 即可

但是我们要先考虑一些问题,如果我们把 \(f(l,r)\) 表示 \([l,r]\) 合并到一起的最大得分

它其实不符合最优子结构性质,因为我们的最大值其实不一定由两个最大值转移过来,它还有可能由两个最小值转移过来

一个最大一个最小(一边都是正数,一边都是负数)

所以如果我们维护 \(f(l, r),g(l,r)\) 分别表示 \([l,r]\) 区间合并到一起的最大,最小值

然后正常进行转移即可

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;typedef long long ll;const int N = 110;int n, val[N];
ll f[N][N], g[N][N];
bool op[N];void cmax (ll &a, ll b) {a = a > b ? a : b;
}
void cmin (ll &a, ll b) {a = a < b ? a : b;
}int main () {cin >> n;char ch;for (int i = 1; i <= n; i ++) {cin >> ch >> val[i];op[i] = ch - 't';}for (int i = n + 1; i <= n * 2; i ++) {val[i] = val[i - n];op[i] = op[i - n];}memset (f, -0x3f, sizeof f);memset (g, 0x3f, sizeof g);for (int i = 1; i <= n * 2; i ++) {f[i][i] = g[i][i] = val[i];}for (int len = 1; len <= n; len ++) {for (int l = 1; l + len - 1 <= n * 2; l ++) {int r = l + len - 1;for (int k = l; k < r; k ++) {if (op[k + 1] == 0) {cmax (f[l][r], f[l][k] + f[k + 1][r]);cmin (g[l][r], g[l][k] + g[k + 1][r]);} else {cmax (f[l][r], f[l][k] * f[k + 1][r]);cmax (f[l][r], g[l][k] * g[k + 1][r]);cmax (f[l][r], f[l][k] * g[k + 1][r]);cmax (f[l][r], g[l][k] * f[k + 1][r]);cmin (g[l][r], g[l][k] * g[k + 1][r]);cmin (g[l][r], g[l][k] * f[k + 1][r]);cmin (g[l][r], f[l][k] * g[k + 1][r]);}}}}ll ma = -4e18;for (int i = 1; i <= n; i ++) {ma = max (ma, f[i][i + n - 1]);}cout << ma << endl;for (int i = 1; i <= n; i ++) {if (f[i][i + n - 1] == ma) {cout << i << ' ';}}return 0;
}
http://www.hskmm.com/?act=detail&tid=25024

相关文章:

  • 12 ACwing 282 石子合并 题解
  • 11 ACwing 281 Coins 题解
  • 某中心科学家荣获多项计算机技术大奖
  • FFT
  • 4 ACwing 274 Mobile Service 题解
  • 3 ACwing 273 Making the Grade 题解
  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16
  • cf296b