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);}}}
}
更多推荐
【对顶栈】HDU 4699 Editor
发布评论