HDU 4699 Editor【栈模拟】

$a[]$记录光标前的内容，

$b[]$记录光标后的内容，

$sum[i]$表示$a[1,i]$的和，

$f[i]$表示$a[1,i]$的最大前缀和。

栈模拟一下就好了。

#include <bits/stdc++.h> using namespace std; const int N=1e6+5; const int Inf=1e9; char ch[5]; int tb,b[N]; int ta,a[N]; int n,f[N],sum[N]; void solve() { ta=tb=0;sum[0]=0;f[0]=-Inf; while(n--) { scanf("%s",ch+1); if(ch[1]=='I') { int x;scanf("%d",&x); a[++ta]=x; sum[ta]=sum[ta-1]+x;f[ta]=max(f[ta-1],sum[ta]); } else if (ch[1]=='L') { if(ta) { int x=a[ta--]; b[++tb]=x; } } else if (ch[1]=='R') { if(tb) { int x=b[tb--]; a[++ta]=x; sum[ta]=sum[ta-1]+x;f[ta]=max(f[ta-1],sum[ta]); } } else if (ch[1]=='Q') { int x;scanf("%d",&x); printf("%d\n",f[x]); } else ta--; } } int main() { while(~scanf("%d",&n)) solve(); return 0; }