正題

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4699

---

大意

有5種操作

1.在光標處寫入一個數字
2.在光標處刪除一個數字
3.4.將光標往 左/右 移動
5.詢問一個位置(光標前)之前的最大前綴和

---

解題思路

我們開兩個棧，一個是存光標前，一個存在光標之后。
然后寫入就壓入第一個棧，刪除就彈出一個棧，光標左移就將第一個棧頂放入第二個棧，右移就將第二個棧放回第一個棧，詢問就用f數組記錄答案，然后直接輸出。

---

code

#include<cstdio> #include<algorithm> #include<iostream> #include<stack> using namespace std; stack<int> a,b; int n,x,sum,f[1000010],tot; char c; int main() {while(scanf("%d",&n)>0){tot=0;f[0]=-2147483647;sum=0;while(!a.empty()) a.pop();while(!b.empty()) b.pop();for(int i=1;i<=n;i++){cin>>c;if(c=='I')//寫入{scanf("%d",&x);a.push(x);tot++;sum+=x;f[tot]=max(f[tot-1],sum);}else if(c=='D'&&!a.empty())//刪除{sum-=a.top();a.pop();tot--;}else if(c=='L'&&!a.empty())//左移{b.push(a.top());sum-=a.top();a.pop();tot--;}else if(c=='R'&&!b.empty())//右移{a.push(b.top());tot++;sum+=b.top();f[tot]=max(f[tot-1],sum);b.pop();}else if(c=='Q')//詢問{scanf("%d",&x);printf("%d\n",f[x]);}}} }

總結

以上是生活随笔為你收集整理的hdu4699-Editor【对顶栈】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。