【对顶栈】HDU 4699 Editor

HDU 4699 Editor"/>

【对顶栈】HDU 4699 Editor

链接

.php?pid=4699

大意

定义多种操作
1.在光标处读入一个字符
2.删除光标前的字符，同时光标左移动
3.光标向左或向右移动一格
4.求光标前的最大子序和

思路

对顶栈

首先我们把两个栈倒过来放，类似一个队列，如图

以样例为例，我们来演示一下对顶栈的实现过程

输入2

输入-1

输入1

查询，即查询最大前缀和

光标左移

删除元素

光标右移

这时4即为答案

流程图制作网站：

代码

#include<algorithm>
#include<cstdio>
#include<stack>
#define re register
#define r(i,a,b) for(re int i=a;i<=b;i++)
using namespace std;int n,x,sum[1000050],sm[1000050],d,p;
char s[10];
stack<int>A,B;
inline int read() 
{int f=0,d=1;char c;while(c=getchar(),c<=47||c>=58) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),c>=48&&c<=57) f=(f<<3)+(f<<1)+c-48;return d*f;
}
inline void write(register int x){if(x<0){x=-x;putchar('-');}if(x>9)write(x/10);putchar(x%10+48);return;}
signed main()
{while(~scanf("%d",&n)){while(A.size()) A.pop();while(B.size()) B.pop();sum[0]=0;sm[0]=-2147483647;p=0;while(n--){scanf("%s",s);if(s[0]=='I'){p++;//p表示A的栈顶所在位置，其实就是A.size()x=read();A.push(x);sum[p]=sum[p-1]+x;sm[p]=max(sm[p-1],sum[p]);}if(s[0]=='D') {if(!p) continue;A.pop();p--;}if(s[0]=='L') {if(!p) continue;B.push(A.top());A.pop();p--;}if(s[0]=='R'){if(B.empty()) continue;p++;A.push(B.top());B.pop();sum[p]=sum[p-1]+A.top();sm[p]=max(sm[p-1],sum[p]);}if(s[0]=='Q'){x=read();write(sm[x]);putchar(10);}}}
}