题解

1 条题解

  • 0
    @ 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

信息

ID
1026
难度
9
分类
动态规划 | 环形DP 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者