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

时间:2021-12-14 09:05:07

本题就是两个要点:

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-;
const int INF=;
const int maxn=+; int n,x;
char op[];
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)==)
{
memset(l,,sizeof(l));
memset(r,,sizeof(r));
memset(sum,,sizeof(sum));
memset(dp,,sizeof(dp));
dp[]=-INF;//这个一定要有
int t1=,t2=;
while(n--)
{
scanf("%s",op);
if(op[]=='I')
{
scanf("%d",&x);
l[++t1]=x;
sum[t1]=sum[t1-]+x;
dp[t1]=max(sum[t1],dp[t1-]);
}
else if(op[]=='L')
{
if(t1==) continue;
r[++t2]=l[t1--];
}
else if(op[]=='R')
{
if(t2==) continue;
l[++t1]=r[t2--];
sum[t1]=sum[t1-]+l[t1];
dp[t1]=max(sum[t1],dp[t1-]);
}
else if(op[]=='D')
{
if(t1==) continue;
t1--;
}
else if(op[]=='Q')
{
scanf("%d",&x);
printf("%d\n",dp[x]);
}
}
}
//fclose(stdin);
//fclose(stdout);
return ;
}