大力分类讨论:
- 没有
- 显然
- 有 :
- 没有
- 没有 :显然
- 有 :找到第一个 (如果存在的话)并在这个 前面一个位置填上 ,其他全部填 。
- 有 的情况是接下来的讨论重点
- 没有
首先注意到如果有 ,则 根本不可能被用到(因为 )
一个很自然的想法是把整个序列以 为分割点,分成几段分别处理。
对于每一段,有一个非常 naive 的 :设 为前 个字符能构成的最大值,每次枚举 ,从 转移到 表示把 中的数乘起来。显然无法通过:不仅会 TLE,数的乘积也会爆 。
考虑几个优化:如果某一段 的乘积大于一个常数 ,则我们直接把 中所有数乘起来。
这个优化可以被形如 的数据卡掉(最后一个 前面应为 ),所以在处理之前需要特判掉首尾的所有 。
官方题解中取 ,实际上 的(并不精确的)下界非常小,只需要确保 即可。详细证明可以参考 arvindr9 的 comment(文末附有这段证明的翻译(这么良心的题解不点个赞吗((
第二个优化是对于 的:预处理 ,表示 之后第一个不是 的数的位置。在 中枚举 时可以直接从 跳到 而不是 。于是这个 的复杂度变成了 ,其中 表示一段中不为 的数的个数。而上一个优化确保了 ,故复杂度正确。
简洁起见,代码删去了缺省源
// 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 :
考虑这个数组(这一段)的最佳分配符号方案。设它的长度为 ,则它可以被表示为如下形式:
其中,每一块(即乘起来的一段连续的数)的首尾元素都大于 。设 。于是,这个数组所有数的乘积为 ,我们设这个乘积为 。不妨假设 。
我们首先想要证明
若 ,则有
若 ,则有
于是我们可以归纳地证明该结论。
于是对于我们当前方案的贡献 ,有
要使 即 ,显然只要满足 即可。