1 条题解
-
0HLBhahaqiu LV 8 MOD @ 2020-08-30 15:26:29
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const long long inf = 0x7fffffffffffffff;
char c[110];
int vis[110][110][2],n; //3-d 0小 1大
long long d[110][110][2],smax,smin=inf;
long long dp(int i,int j,int f){ //左闭右开
long long &ans = d[i][j][f];
if(vis[i][j][f]) return ans;
vis[i][j][f] = 1;
if(i+1==j) return ans;
for(int k=i+1;k<j;k++){
if(f) ans = max(ans,c[k-1]=='*'?max(dp(i,k,1)*dp(k,j,1),dp(i,k,0)*dp(k,j,0)):dp(i,k,1)+dp(k,j,1));
else ans = min(ans,c[k-1]=='*'?min(min(dp(i,k,0)*dp(k,j,0),dp(i,k,1)*dp(k,j,1)),min(dp(i,k,1)*dp(k,j,0),dp(i,k,0)*dp(k,j,1))):dp(i,k,f)+dp(k,j,f));
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;i++){
cin>>c[i];
c[n+i] = c[i];
}
for(int i=0;i<2*n;i++) for(int j=0;j<2*n;j++) d[i][j][0] = inf,d[i][j][1]=-inf;
for(int i=0;i<n;i++){
cin>>d[i][i+1][0];
d[i+n][i+n+1][1] = d[i+n][i+n+1][0] = d[i][i+1][1] = d[i][i+1][0];
}
for(int i=0;i<n;i++){
smax = max(smax,dp(i,i+n,1));
smin = min(smin,dp(i,i+n,0));
}
cout<<smax<<'\n'<<smin;
return 0;
}
//要用万能头
- 1