HDU 4699 Editor【模拟栈】-白红宇

HDU 4699 Editor【模拟栈】

阅读量：5063 次

发布时间：2019-06-12

本文共 1752 字，大约阅读时间需要 5 分钟。

反正当时是没有想到怎么做，但发现用栈模拟后就有思路了。

题意就是找光标前的位置的最大前缀和，那最朴素的实现就是拿数组模拟，每一次insert和delete都重新更新一下maxprev和sum和整个序列的值；后来发现maxprev和sum不用每次都更新，而是只要保证光标pos位置前的值都对就可以了（因为询问只关心了前pos位的最大前缀和），但即便是这样还是得O(n)更新insert的delete（因为要维护a数组）。

这个时候就要有stack的思想了，s1栈从底下到上面为1到光标之间的数，然后s2从最上面到最底下是从光标后一位到序列的最后一个数。

所以就能做到O(1)更新了。

1.注意下用了关同步的优化就不能用scanf，printf；不然会出现说不清楚的错误

2.输入用char不用char数组的话小心换行符

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
              #include
             
              #include
              
               #define INF 2e9#define maxnode 100000#define ll long long#define lowbit(x) (x&(-x))int dx[4]={ 0,0,1,-1};int dy[4]={ 1,-1,0,0};using namespace std;int maxprev[1000005],sum[1000005];stack
               
                 s1,s2;int main(){ //ios::sync_with_stdio(false); int q; while( ~scanf("%d",&q) ){ int pos=0,len=0; maxprev[0]=-INF; //memset(maxprev,0,sizeof(maxprev)); //memset(sum,0,sizeof(sum)); while( !s1.empty() ) s1.pop(); while( !s2.empty() ) s2.pop(); //s1里面存cursor前的数 //s2里面存cursor后的数 //任意时刻maxprev[pos]和sum[pos]都是合法的 for(int i=1;i<=q;i++){ char op[5]; scanf("%s",op); if( op[0]=='I' ){ int num; scanf("%d",&num); s1.push( num ); //把num放在s1的首 pos++; sum[pos]=sum[pos-1]+num; maxprev[pos]=max( maxprev[pos-1],sum[pos] ); } else if( op[0]=='D' ){ s1.pop(); pos--; } else if( op[0]=='L' ){ if( s1.empty() ) continue; pos--; int tmp=s1.top(); s1.pop(); s2.push(tmp); //不用计算新的maxprev } else if( op[0]=='R' ){ if( s2.empty() ) continue; int tmp=s2.top(); s2.pop(); s1.push(tmp); sum[pos+1]=sum[pos]+s1.top(); maxprev[pos+1]=max( maxprev[pos],sum[pos+1] ); pos++; } else if( op[0]=='Q' ){ int k; scanf("%d",&k); printf("%d\n",maxprev[k]); } } } return 0;}

转载于:https://www.cnblogs.com/ZhenghangHu/p/9759435.html

你可能感兴趣的文章