单调栈求每个数在哪些区间是最值的经典操作。
poj的话直接求区间和*区间min就好了
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int M=150007; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n,w[M]; int stk[M],top; int ansl,ansr; LL ans=-1,sum[M]; int main() { n=read(); for(int i=1;i<=n;i++) w[i]=read(),sum[i]=sum[i-1]+w[i]; w[++n]=-1; for(int i=1;i<=n;i++){ while(top&&w[i]<=w[stk[top]]){ LL h=(sum[i-1]-sum[stk[top-1]])*1LL*w[stk[top]]; if(h>ans) ans=h,ansl=stk[top-1]+1,ansr=i-1; top--; } stk[++top]=i; } printf("%lld %d %d ",ans,ansl,ansr); return 0; }
51nod 的话就是求mx和 以及 mn和贡献相减就好辣
考虑每个数以及他能覆盖的最大区间 他的贡献明显是以他的中心 左区间长度乘右区间长度乘他本身的值
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int M=50007,inf=0x3f3f3f3f; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n,w1[M],w2[M]; int sk1[M],tp1,sk2[M],tp2; LL mx,mn; int main() { n=read(); for(int i=1;i<=n;i++) w1[i]=w2[i]=read(); n++; w1[n]=inf; w2[n]=-1; for(int i=1;i<=n;i++){ while(tp1&&w1[i]>=w1[sk1[tp1]]) mx+=1LL*w1[sk1[tp1]]*(i-sk1[tp1])*(sk1[tp1]-sk1[tp1-1]),tp1--; while(tp2&&w2[i]<=w2[sk2[tp2]]) mn+=1LL*w2[sk2[tp2]]*(i-sk2[tp2])*(sk2[tp2]-sk2[tp2-1]),tp2--; sk1[++tp1]=sk2[++tp2]=i; } printf("%lld ",mx-mn); return 0; }