hdu4699 Editor(双向链表或双栈对弹)

本题就是两个要点：

1.数据结构的设计。显然可以使用双向链表来做，但是写双向链表的代码复杂度高。其实更好的方法是使用两个对弹的栈来做，而且没必要用STL的栈，就自己开两个数组简单搞一下就好了。

2.最大前缀和的更新。很简单的递推关系，dp[i]=max(dp[i-1],sum[i])，意思是从开头到a[i]的最大前缀和里，要么没有i（即dp[i-1]），要么有i(即sum[i])。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<deque>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<cctype>
#include<sstream>
using namespace std;
#define pii pair<int,int>
#define LL long long int
const double eps=1e-10;
const int INF=1000000000;
const int maxn=1000000+10;

int n,x;
char op[3];
int l[maxn],r[maxn],sum[maxn],dp[maxn];

int main()
{
    //freopen("in2.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d",&n)==1)
    {
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        dp[0]=-INF;//这个一定要有
        int t1=0,t2=0;
        while(n--)
        {
            scanf("%s",op);
            if(op[0]=='I')
            {
                scanf("%d",&x);
                l[++t1]=x;
                sum[t1]=sum[t1-1]+x;
                dp[t1]=max(sum[t1],dp[t1-1]);
            }
            else if(op[0]=='L')
            {
                if(t1==0) continue;
                r[++t2]=l[t1--];
            }
            else if(op[0]=='R')
            {
                if(t2==0) continue;
                l[++t1]=r[t2--];
                sum[t1]=sum[t1-1]+l[t1];
                dp[t1]=max(sum[t1],dp[t1-1]);
            }
            else if(op[0]=='D')
            {
                if(t1==0) continue;
                t1--;
            }
            else if(op[0]=='Q')
            {
                scanf("%d",&x);
                printf("%d
",dp[x]);
            }
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}