bzoj1106 树状数组

https://www.lydsy.com/JudgeOnline/problem.php?id=1106

一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的，所以我们只介绍他的简单规

则：给定玩家一个有2n个元素的栈，元素一个叠一个地放置。这些元素拥有n个不同的编号，每个编号正好有两个

元素。玩家每次可以交换两个相邻的元素。如果在交换之后，两个相邻的元素编号相同，则将他们都从栈中移除，

所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。

题意

贪心的想到每一对当前匹配的费用是他们之间未匹配的数字的个数。

第一个想法是每次取出费用最小的对进行匹配，每次产生r - l - 1的费用，直到全部匹配，但是这样怎么看都觉得会T，事实上每次并不需要总是取出最小的来匹配。

也就是说当状态时1234512345 678876的时候，左边和右边的操作事实上是相互独立的，先后顺序并不干扰，所以我们只要从前向后遍历，第一个和前面有匹配的数字就是当前状态的最优对数，我们直接将他消去，更新他们之间数字的费用即可。

操作用BIT维护一下就好了

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 5e4 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,tmp,K;

int tree[maxn * ];

void add(int x,int t){

    for(;x <= N * ;x += x & -x) tree[x] += t;

}

int getsum(int x){

    int s = ;

    for(;x > ;x -= x & -x) s += tree[x];

    return s;

}

int vis[maxn];

int main()

{

    Sca(N);

    int cnt = ;

    int ans = ;

    For(i,,N * ){

        int x; Sca(x);

        if(!vis[x]){

            cnt++;

            vis[x] = i;

            add(i,);

        }else{

            ans += cnt - getsum(vis[x]);

            cnt--;

            add(vis[x],-);

        }

    }

    Pri(ans);

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}

秒客网

bzoj1106 树状数组

相关文章