除了维护一个区间最大值,还要一个最小值,( 有负数)
#include <iostream> #include <algorithm> #include <cstring> using namespace std ; const int N=160; #define inf 1e9 int n,a[N],f[N][N],g[N][N]; char op[N] ; signed main(){ int i,j,k; cin>>n; for(i=1;i<=n;i++){ cin>>op[i]>>a[i],a[i+n]=a[i],op[i+n]=op[i]; } for(i=1;i<=n*2;i++) for(j=1;j<=n*2;j++) f[i][j]=-inf,g[i][j]=inf; for(i=1;i<=n*2;i++) f[i][i]=g[i][i]= a[i]; for(int len=2;len<=n;len++) for(i=1;i+len-1<=2*n;i++){ j=i+len-1; for(k=i;k<j;k++){ if(op[k+1]=='t'){ f[i][j]= max(f[i][j],f[i][k]+f[k+1][j]); g[i][j]= min(g[i][j], g[i][k]+g[k+1][j]); } else{ f[i][j]=max(f[i][j],max(f[i][k]*f[k+1][j], max(f[i][k]*g[k+1][j],max(g[i][k]*f[k+1][j], g[i][k]*g[k+1][j])))); g[i][j]=min(g[i][j],min(f[i][k]*f[k+1][j], min(f[i][k]*g[k+1][j],min(g[i][k]*f[k+1][j], g[i][k]*g[k+1][j])))); } } } int ans= -inf; for(i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]); cout<<ans<<endl; for(i=1;i<=n;i++) if(f[i][i+n-1]==ans) cout<<i<<' '; }
标签:Polygon,int,1179,POJ,include,op From: https://www.cnblogs.com/towboa/p/17205627.html