bzoj1106[POI2007]立方體大作戰tet

題意：

給定玩家一個有2n個元素的棧，這些元素擁有n個不同的編號，每個編號正好有兩個元素。玩家每次可以交換兩個相鄰的元素。如果在交換之后，兩個相鄰的元素編號相同，則將他們都從棧中移除，所有在他們上面的元素都會掉落下來并且可以導致連鎖反應。求最少的步數將方塊全部消除。

題解：

用一個棧維護，如果遇到一個沒有遇到過的編號就入棧，否則就讓之前的那個元素出棧，兩個元素之間的元素向下移一位，并將兩個元素的距離計入答案。

代碼：

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 100010 6 using namespace std; 7 8 inline int read(){ 9 char ch=getchar(); int f=1,x=0; 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} 11 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); 12 return f*x; 13 } 14 int st[maxn],top,ans,n; bool in[maxn]; 15 int main(){ 16 n=read(); 17 inc(i,1,2*n){ 18 int x=read(); 19 if(!in[x])in[x]=1,st[++top]=x;else{ 20 int j=top; while(st[j]!=x)j--; inc(k,j,top-1)st[k]=st[k+1],ans++; top--; in[x]=0; 21 } 22 } 23 printf("%d",ans); return 0; 24 }

?

20160810

轉載于:https://www.cnblogs.com/YuanZiming/p/5769470.html

總結

以上是生活随笔為你收集整理的bzoj1106[POI2007]立方体大作战tet*的全部內容，希望文章能夠幫你解決所遇到的問題。

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