【题解】CF1461F

大力分类讨论：

• 没有 $\texttt{*}$
  • 显然
• 有 $\texttt{*}$：
  • 没有 $\texttt{+}$
    • 没有 $\texttt{-}$：显然
    • 有 $\texttt{-}$：找到第一个 $0$（如果存在的话）并在这个 $0$ 前面一个位置填上 $\texttt{-}$，其他全部填 $\texttt{*}$。
  • 有 $\texttt{+}$ 的情况是接下来的讨论重点

首先注意到如果有 $\texttt{+}$，则 $\texttt{-}$ 根本不可能被用到（因为 $0 \le a_i \le 9$）

一个很自然的想法是把整个序列以 $0$ 为分割点，分成几段分别处理。

对于每一段，有一个非常 naive 的 $n^2$ $dp$：设 $dp_i$ 为前 $i$ 个字符能构成的最大值，每次枚举 $j$，从 $dp_i$ 转移到 $dp_j$ 表示把 $[i,j]$ 中的数乘起来。显然无法通过：不仅会 TLE，数的乘积也会爆 $\texttt{long long}$。

考虑几个优化：如果某一段 $[l,r]$ 的乘积大于一个常数 $P$，则我们直接把 $[l,r]$ 中所有数乘起来。

这个优化可以被形如 $9,9,9 \cdots 9,1$ 的数据卡掉（最后一个 $1$ 前面应为 $\texttt{+}$），所以在处理之前需要特判掉首尾的所有 $1$。

官方题解中取 $P=10^{16}$，实际上 $P$ 的（并不精确的）下界非常小，只需要确保 $P \ge 2n$ 即可。详细证明可以参考 arvindr9 的 comment（文末附有这段证明的翻译（这么良心的题解不点个赞吗（（

第二个优化是对于 $dp$ 的：预处理 $\texttt{next}_i$，表示 $i$ 之后第一个不是 $1$ 的数的位置。在 $dp$ 中枚举 $j$ 时可以直接从 $j$ 跳到 $\texttt{next}_j$ 而不是 $j+1$。于是这个 $dp$ 的复杂度变成了 $\mathcal{O(len \cdot x)}$，其中 $x$ 表示一段中不为 $1$ 的数的个数。而上一个优化确保了 $x \le \log_2 P$，故复杂度正确。

简洁起见，代码删去了缺省源

// 2020.12.13
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define debug puts("QwQ");

const int MAXN=100005;
int n;
int a[MAXN];
bool Plus,Minus,Multiple;
int dp[MAXN],bel[MAXN];
char ans[MAXN];
int nex[MAXN];
int P=1e7;

void sol1(){
	for (int i=2;i<=n;i++)
		if (Plus) ans[i]='+';
		else ans[i]='-';
}

void sol2(){
	for (int i=2;i<=n;i++)
		ans[i]='*';
}

void sol3(){
	int pos=0;
	for (int i=1;i<=n;i++)
		if (!pos && a[i]==0) pos=i;

	for (int i=2;i<=n;i++){
		if (i==pos) ans[i]='-';
		else ans[i]='*';
	}
}

void init(){
	int cur=0;
	for (int i=n;i>=1;i--){
		nex[i]=cur;
		if (a[i]!=1) cur=i;
	}
}

void foo(int l,int r){
	int cnt=1;
	dp[l-1]=0;
	for (int i=l;i<=r;i++){
		if (cnt<P) cnt*=a[i];
		dp[i]=bel[i]=0;
	}

	if (cnt>=P){
		for (int i=l+1;i<=r;i++)
			ans[i]='*';
		return ;
	}

	for (int i=l;i<=r;i++){
		cnt=1;
		for (int j=i;j<=r && j;j=nex[j]){
			cnt*=a[j];
			if (dp[i-1]+cnt>dp[j]){
				dp[j]=dp[i-1]+cnt;
				bel[j]=i-1;
			}
		}
	}

	int cur=r;
	while (cur>=l){
		int tmp=bel[cur];
		ans[tmp+1]='+';
		for (int i=tmp+2;i<=cur;i++)
			ans[i]='*';

		cur=tmp;
	}
}

void sol4(){
	init();
	for (int i=1;i<=n;i++){
		if (a[i]==0){
			ans[i+1]=ans[i]='+';
			continue;
		}

		int cur=i;
		while (cur<n && a[cur+1]!=0) cur++;

		int l=i,r=cur;
		while (l<=r && a[l]==1) ans[++l]='+';
		while (l<=r && a[r]==1) ans[r--]='+';
		if (l<=r) foo(l,r);
		i=cur;
	}
}

void print(){
	cout<<a[1];
	for (int i=2;i<=n;i++)
		cout<<ans[i]<<a[i];
	cout<<endl;
}

signed main()

{
	n=read();P=2*n;
	for (int i=1;i<=n;i++)
		a[i]=read();

	string allowed=readstr();
	for (auto i:allowed){
		if (i=='+') Plus=true;
		else if (i=='-') Minus=true;
		else Multiple=true;
	}

	if (!Multiple) sol1();
	else{
		if (!Plus && !Minus) sol2();
		else if (!Plus) sol3();
		else sol4();
	}

	print();
	return 0;
}

Proof :

考虑这个数组（这一段）的最佳分配符号方案。设它的长度为 $n$，则它可以被表示为如下形式：

$(d_{1_1} \cdot d_{1_2} \cdot d_{1_3} \dots ) + 1 + 1 + \dots 1 + (d_{2_1} \cdot d_{2_2} \dots ) + 1 + 1 +\dots + (d_{k_1} \cdot d_{k_2} \dots )$

其中，每一块（即乘起来的一段连续的数）的首尾元素都大于 $1$。设 $a_i = \prod\limits_j d_{i_j}$。于是，这个数组所有数的乘积为 $\prod\limits_{i=1}^k a_i$，我们设这个乘积为 $P$。不妨假设 $k\ge 2$。

我们首先想要证明

$\sum\limits_{i=1}^k a_i \leq 2 + \frac{P}{2}$

若 $k=2$，则有

$a_1 + a_2 = a_1 + \frac{P}{a_1} \le 2 + \frac{P}{2}$

若 $k>2$，则有

$\sum\limits_{i=1}^k a_i \le (\sum\limits_{i=1}^{k-2}a_i) + a_{k-1} \cdot a_{k}$

于是我们可以归纳地证明该结论。

于是对于我们当前方案的贡献 $W$，有

$W \le \sum\limits_{i = 1}^k a_i + \text{1的个数} \le 2 + \frac{P}{2} + n - k \le \frac{P}{2} + n$

要使 $W \le P$ 即 $\frac{P}{2} + n \le P$，显然只要满足 $P \ge 2n$ 即可。