分析 : 简单的单调栈
两份代码,第一份错的,第二份对的
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 4; struct Node { ll h,v,w; }pp[maxn]; stack<Node> sta; ll max(ll a,ll b){return a>b?a:b;} int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&pp[i].h,&pp[i].v),pp[i].w=0; sta.push(pp[1]); //错的点,此时塞进去的不是pp[1],只是一个各属性和pp[1]相同的Node,所以下面修改栈顶Node的属性的时候,pp数组是没有变化的!!!!!! ll ans=0; for(int i=2;i<=n;i++) { while(!sta.empty()&&sta.top().h<=pp[i].h) { if(sta.top().h==pp[i].h) pp[i].v+=sta.top().v; else pp[i].w+=sta.top().v; sta.pop(); } if(!sta.empty()) sta.top().w+=pp[i].v; sta.push(pp[i]); } for(int i=1;i<=n;i++) ans=max(ans,pp[i].w); printf("%lld",ans); return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 4; struct Node { ll h,v,w; }pp[maxn]; stack<int> sta; ll max(ll a,ll b){return a>b?a:b;} int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&pp[i].h,&pp[i].v),pp[i].w=0; sta.push(1); ll ans=0; for(int i=2;i<=n;i++) { while(!sta.empty()&&pp[sta.top()].h<=pp[i].h) { if(pp[sta.top()].h==pp[i].h) pp[i].v+=pp[sta.top()].v; else pp[i].w+=pp[sta.top()].v; sta.pop(); } if(!sta.empty()) pp[sta.top()].w+=pp[i].v; sta.push(i); } for(int i=1;i<=n;i++) ans=max(ans,pp[i].w); printf("%lld",ans); return 0; }