Bzoj1106 [poi2007]立方体大作战tet

Posted by yjjr's blog on December 20, 2017

标签:贪心,栈

题目

题目传送门

Description

  一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的,所以我们只介绍他的简单规 则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置。这些元素拥有n个不同的编号,每个编号正好有两个 元素。玩家每次可以交换两个相邻的元素。如果在交换之后,两个相邻的元素编号相同,则将他们都从栈中移除, 所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。 Input

  第一行包含一个正整数n(1<=n<=50000)。接下来2n行每行一个数ai,从上到下描述整个栈,保证每个数出现且 仅只出现两次(1<=ai<=n)。初始时,没有两个相同元素相邻。并且保证所有数据都能在1000000步以内出解。 Output

  第一行包含一个数m,表示最少的步数。 Sample Input 样例输入1

5

5

2

3

1

4

1

4

3

5

2

样例输入2

3

1

2

3

1

2

3

Sample Output 样例输出1

2

样例输出2

3

分析

对于12XXXX21这种形式的序列来说,我们合并2一定比合并1更优,所以对于嵌套关系的先删去中间的那对最优

对于12XX12这样相交关系的序列来说,合并1和2对答案不会产生影响

这样的贪心很显然是正确的

然后就维护一个栈解决

这题在洛谷上也有P3460,但是多了一问要输出方案

调了一整天都没A掉输出方案的版本(我题意理解错了)

输出方案是重新构成的序列中的位置

然而我自己写spj感觉应该是原序列中的位置(因为检验重新构成的序列中的位置spj版本不好写啊,或许是我太弱)

有没有大佬还看下那道题,欢迎下面评论啊


终于A掉这题了(洛谷上带有方案的版本)

这题spj原来要用平衡树/链表+线段树 写

zyl说这是全站第三难写的spj orz

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
const int maxn=1e5+6;
int a[maxn],vis[maxn],top=0,ans=0,cnt=0,n;
struct node{int val,pos;}s[maxn];
int main()
{
    n=read();
    rep(i,1,2*n){
        int x=read();
        if(!vis[x]){vis[x]=1;s[++top].val=x;s[top].pos=i;}
        else{
            int k=0;
            dep(j,top,1)
                if(s[j].val==x){k=j;break;}
            ans+=top-k;if(top!=k)a[++cnt]=s[k].pos;top--;
            //cout<<k<<' '<<top<<' '<<ans<<endl;
            rep(j,k,top)s[j]=s[j+1];
        }
    }
    printf("%d\n",ans);
    //rep(i,1,cnt)printf("%d\n",a[i]);
    return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr