HDOJ 4699-Editor[栈]

Problem Description

Sample Input
8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

Sample Output
2
3
Hint
The following diagram shows the status of sequence after each instruction:

.
.
.
.
.

分析

5种操作，在光标后面加一个数，删除光标前面的一个数，将光标左右移动，求光标从1-k连续子区间和最大。

用两个栈来维护，一个栈来维护光标前面，另一个栈来维护光标后面，然后对第一个栈，增加或者减少数来更新f数组就行了。
.
.
.
.
.

程序：

#include<iostream>
#include<stack>
#include<stdio.h>
using namespace std;
int f[2000000];

int main()
{
    char ch,zfc[200];
    int n;
    while (scanf("%d",&n)!=EOF) 
    {
        stack <int> a;
        stack <int> b;
        int sum=0,x;
        f[0]=-999999999;
        while (n--)
        {
            scanf("%s",zfc);
            ch=zfc[0];
            if (ch=='I')
            {
                scanf("%d",&x);
                a.push(x);
                sum+=x;
                int l=a.size();
                f[l]=max(sum,f[l-1]);
            } else
            if (ch=='D'&&a.size()>=1)
            {
                x=a.top();
                a.pop();
                sum-=x;
            } else
            if (ch=='L'&&a.size()>=1)
            {
                x=a.top();
                a.pop();
                sum-=x;
                b.push(x);
            } else
            if (ch=='R'&&b.size()>=1)   
            {
                x=b.top();
                b.pop();
                a.push(x);
                sum+=x;
                int l=a.size();
                f[l]=max(sum,f[l-1]);
            } else 
            if (ch=='Q')
            {
                scanf("%d",&x);
                printf("%d
",f[x]);
            }
        }
    }
    return 0;
}