题意
给定长度为 \(n\) 的数列 \(a\)。以及字符串 \(S\)。
你需要在每一个数字之间插入一个字符 \(x \in S\)。
求使得最终表达式的值最大的方案。
\(S \in [+, -, *]\)
Sol
考虑分讨。
当 \(|S| = 1\) 时，直接填入即可。
当 \(S \in [+, -]\) 时，发现只有 \(+\) 号有贡献，不难推出当 \(+, -\) 都存在时的情况都等价于只有 \(+\)。
当 \(S \in [-, *]\) 时，第一次出现 \(0\) 时，插入一次 \(-\)，后面全部插入 \(*\) 即可。
当 \(S \in [+, *]\) 或 \(S \in [+, -, *]\) 时：
首先先考虑 \(0\)，不难发现 \(a_i = 0\) 会将数列分成若干段，这些段互不影响。
我们对每一段分别考虑，注意到如果当前段的 \(\sum [a_i > 1] > 30\) 时，当前段的最优解，一定是全部乘起来，证明显然是 \(trivial\) 的。
我们考虑对于每一个 \(a_i > 1\) 的位置做一个简单 \(dp\)。枚举上一个加的位置。
总复杂度 \(O(n log n)\)。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <vector>
#define int __int128
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
string read_() {
string ans;
char c = getchar();
while (c != '+' && c != '-' && c != '*')
c = getchar();
while (c == '+' || c == '-' || c == '*') {
ans += c;
c = getchar();
}
return ans;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 1e5 + 5;
array <int, N> s;
int n, op;
namespace Subtask1 {
signed main() {
for (int i = 1; i < n; i++) {
write(s[i]);
if (op == 1) putchar('*');
if (op == 2) putchar('+');
if (op == 4) putchar('-');
}
write(s[n]), puts("");
return 0;
}
}
namespace Subtask2 {
signed main() {
for (int i = 1; i < n; i++)
write(s[i]), putchar('+');
write(s[n]), puts("");
return 0;
}
}
namespace Subtask3 {
signed main() {
bool flg = 0;
write(s[1]);
for (int i = 2; i <= n; i++) {
if (s[i] && !flg) putchar('*');
else if (!s[i] && !flg) flg = 1, putchar('-');
else putchar('*');
write(s[i]);
}
puts("");
return 0;
}
}
namespace Subtask4 {
array <int, N> ans;
array <pii, N> isl;
array <int, N> f, pre;
signed main() {
s[n + 1] = 0;
int lst = 1;
for (int i = 1; i <= n + 1; i++) {
if (s[i] != 0) continue;
int l = lst, r = i - 1;
ans[i] = '+'; ans[i - 1] = '+';
while (s[l] == 1) {
ans[l] = '+';
l++;
}
while (s[r] == 1) {
r--;
ans[r] = '+';
}
vector <int> isl;
for (int i = l; i <= r; i++) {
if (s[i] == 1) continue;
isl.push_back(i);
}
if (isl.size() > 30) {
for (int i = l; i < r; i++)
ans[i] = '*';
lst = i + 1;
continue;
}
f[l - 1] = 0;
for (int i = l; i <= r; i++) {
int tp = 1;
if (s[i] == 1) {
f[i] = f[i - 1] + 1;
pre[i] = i - 1;
continue;
}
for (int j = isl.size() - 1; ~j; j--) {
if (isl[j] > i) continue;
tp *= s[isl[j]];
if (tp + f[isl[j] - 1] <= f[i]) continue;
f[i] = tp + f[isl[j] - 1];
pre[i] = isl[j] - 1;
}
}
int kl = r;
while (kl >= l) {
for (int i = pre[kl] + 1; i < kl; i++)
ans[i] = '*';
ans[pre[kl]] = '+';
kl = pre[kl];
}
lst = i + 1;
}
for (int i = 1; i <= n; i++) {
write(s[i]);
if (i != n) putchar(ans[i]);
}
return 0;
}
}
signed main() {
/*freopen("max.in", "r", stdin);*/
/*freopen("max.out", "w", stdout);*/
n = read();
for (int i = 1; i <= n; i++)
s[i] = read();
string str = read_(); op = 0;
for (auto x : str) {
if (x == '*') op += 1;
if (x == '+') op += 2;
if (x == '-') op += 4;
}
if (op == 1 || op == 2 || op == 4) return Subtask1::main();
if (op == 3 || op == 7) return Subtask4::main();
if (op == 6) return Subtask2::main();
if (op == 5) return Subtask3::main();
return 0;
}