问题描述

题解思路

大致思路：

利用双栈进行维护，光标左边为一个栈，光标右边为一个栈。遇到I的时候就将其假如左边的栈，遇到D就删去左边栈的栈顶元素，遇到R就将右边栈顶的元素假如左边栈，遇到L就将左边栈顶元素假如右边栈中，遇到Q就输出前k个元素中和最大的值（此处用动态规划的方法每次当元素进入左栈的时候就记录该元素以前的最大和）。就这样依次输出就好了。

具体实现：

两个数组，一个为左栈，一个为右栈，遇到相应的字符就进行相应的操作，跟大致思路里面一样，用两个指针就可以实现。对于求和问题，就利用动态规划的思想，左栈每进入一个元素就记录到这个元素为止的最大和，用一个数组记录，然后遇到Q就输出相应的值。

注意事项：

（1）注意数组的初始化。

（2）注意如果光标到最左边或是到最右边，即左栈或是右栈元素为0的时候就不需要进行相关操作了。

实现代码

<span style="font-family:Microsoft YaHei;font-size:14px;">#include<stdio.h>
#include<string.h>
int max(int x,int y)
{if(x>y){return x;}else{return y;}
}
int dp[1000010],he[1000010];               //动态规划的思想计算前面书和最大 
int left[1000010],right[1000010];    //使用双栈 
int main()
{int n,l,r,i,x,k;char temp[2];while(scanf("%d",&n)!=EOF){memset(dp,0,sizeof(dp));memset(he,0,sizeof(he));memset(temp,0,sizeof(temp));dp[0]=-1000010;l=0;r=0;for(i=0;i<n;i++){scanf("%s",temp);      //防止空格和回车键的影响用%s读入,这样就不需要考虑空格和回车键 if(temp[0]=='I'){scanf("%d",&x);l++;left[l]=x;//	l++;he[l]=he[l-1]+x;            //添加数到左边,并用动态规划的思想记录前l个数的最大和 dp[l]=max(he[l],dp[l-1]);}else if(temp[0]=='D'){if(l!=0){l--;}//移动指针,删除元素 }else if(temp[0]=='L'){if(l!=0){r++;right[r]=left[l];l--;//	r++;                 //左移光标,利用指针的变化,对两个栈进行入栈和出栈的操作//	l--;}}else if(temp[0]=='R'){if(r!=0){l++;left[l]=right[r];//l++;r--;he[l]=he[l-1]+left[l];         dp[l]=max(he[l],dp[l-1]);       //右移光标,利用指针的变化,对两个栈进行入栈和出栈操作,并对左侧的和进行更新 //	l++;//	r--;}}else if(temp[0]=='Q'){scanf("%d",&k);if(l==0){printf("0\n");}else{printf("%d\n",dp[k]);}}else;	}}return 0;		
}</span>