Codeforces1461F.Mathematical Expression
题意
给定一个长度为(n)的整数数组(a)和一个长度不大于(3)的由运算符组成的字符串(s)，让你在(a)中所有相邻的数字之间添加一个(s)中的运算符，使这个算术表达式的值最大。
(nle 10^5,0le a_i le 9)，(s)由"-","+","*"组成。
分析
当(s)中只包括一种运算符时，只能填充这个运算符，"+-*"可以等价于"+*"，“+-”等价于"+"，那么就只剩下两种情况。
- “-*"，两个大于(0)的数之间一定是填充"*"，设(x>0)，(0x)之间若填充”-“会出现负数，所以要用"*"，(x0)之间用"-"。
- "+*"，对于这种情况，我们以(0)作为分割点，(0)的两边一定是"+"，对于分割出的每一段分别考虑，假设某一段在原数组中为区间([l,r])，对于这个区间开头的一段(1)和结尾的一段(1)每个数字之间都填充"+"，对于中间的一段我们自然可以想到若它们的乘积非常大(大于(10^{16}))，一定是全部乘起来，否则对于(2,3,1,1,cdots,1,1,2,3)这种中间有很长的一段(1)的数据，(2 imes 3+1+1+cdots+1+1+2 imes 3)这样会更大，考虑动态规划，设(dp[i])表示前(i)个数后已经添加运算符的最大值，从(i)转移到(j(j>i))，有两种情况，([i+1,j-1])这一段每个数字后面都填充加号或者都填充乘号，这一段后添加加号，这样是(n^2)的，因为连续的一段(1)一定是全部加起来或者和两边乘起来，设(nex[i])表示(i)所在连续(1)的段的段尾，(j)就可以不断的跳(max(j+1,nex[i]))来加速转移，因为这个区间所有数字乘起来都不大于(10^{16})，所以(j)最多跳(log(10^{16}))次，记录转移的前驱，回溯更新答案即可。
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const ll inf=1e16;
int n,a[N];
vector<int>w;
string s;
ll pre[N],sum[N],dp[N];
int f[N],nex[N];
char c[N];
char ans[N];
void gao(int l,int r){
int dl=l,dr=r;
while(a[dl]==1&&dl<=r){
ans[dl]='+';
++dl;
}
while(a[dr]==1&&l<=dr){
ans[dr]='+';
--dr;
}
l=dl,r=dr;
if(l>r) return;
pre[l-1]=1;
sum[l-1]=0;
int flag=0;
rep(i,l,r){
pre[i]=pre[i-1]*a[i];
sum[i]=sum[i-1]+a[i];
if(pre[i]>inf){
flag=1;
break;
}
}
if(flag){
rep(i,l,r-1) ans[i]='*';
ans[r]='+';
return;
}
int now=l;
rep(i,l,r){
now=max(now,i);
while(a[now]==1&&now<=n) ++now;
if(now==i) nex[i]=now;
else nex[i]=now-1;
}
rep(i,l-1,r) dp[i]=0;
rep(i,l-1,r-1){
for(int j=i+1;j<=r;j=max(j+1,nex[j])){
if(pre[j]/pre[i]+dp[i]>dp[j]){
dp[j]=pre[j]/pre[i]+dp[i];
f[j]=i;
c[j]='*';
}
if(sum[j]-sum[i]+dp[i]>dp[j]){
dp[j]=sum[j]-sum[i]+dp[i];
f[j]=i;
c[j]='+';
}
}
}
now=r;
while(now!=l-1){
int x=f[now];
rep(i,x+1,now-1) ans[i]=c[now];
ans[now]='+';
now=x;
}
}
int main(){
//ios::sync_with_stdio(false);
//freopen("in","r",stdin);
cin>>n;
rep(i,1,n) cin>>a[i];
cin>>s;
if(sz(s)==1){
rep(i,1,n-1){
cout<<a[i]<<s[0];
}
cout<<a[n]<<endl;
}else if(s=="+-"||s=="-+"){
rep(i,1,n-1){
cout<<a[i]<<"+";
}
cout<<a[n]<<endl;
}else if(s=="+*"||s=="*+"||sz(s)==3){
int l=1;
for(int i=1;i<=n;i++){
if(a[i]==0){
if(l<=i-1) gao(l,i-1);
ans[i]='+';
l=i+1;
}
}
if(l<=n) gao(l,n);
rep(i,1,n-1) cout<<a[i]<<ans[i];
cout<<a[n]<<endl;
}else if(s=="-*"||s=="*-"){
cout<<a[1];
rep(i,2,n){
if(a[i-1]>0&&a[i]==0) cout<<'-';
else cout<<"*";
cout<<a[i];
}
cout<<endl;
}
return 0;
}