codechef [snackdown2017 Onsite Final] Fusing Weapons

传送门

题目描述

　　大厨最近迷上了一款勇者斗恶龙的游戏。 游戏每局开始前，会有 N 件武器摆成一圈。每件武器有一个整数的等级。大厨可以选择两件 相邻的等级相同（不妨设同为 A 级）的武器，将它们合成。这两件武器在合成后就消失了，取而 代之，在它们原本所在的位置上出现的是一件 A + 1 级的武器。 大厨可以合成任意多次，而游戏的目标就是合成出尽可能高等级的武器。每关之间互不影响。 请你帮大厨求出每局游戏能合成得到武器的最高等级。

输入格式

　　输入第一行，包含一个整数 T，表示游戏局数。下面是 T 局游戏的描述。 每局的描述中，第一行包含一个整数 N，代表初始时武器的数量。第二行包含 N 个整数 L1, . . . , LN，依次代表第 1 到第 N 件武器的初始等级。第 i 和第 i + 1 (1 ≤ i < N) 件武器相邻， 而且第 N 和第 1 件武器相邻。

输出格式

　　对于每局游戏，输出一行，包含一个整数，代表大厨能合成出的武器的最高等级。

　　没什么想法啊，膜了膜别人的AC代码

　　大概意思就是先把序列倍长，然后从低等级到高等级枚举，每个位置记录以这个点为终点的合并后最大等级，注意不要越界就好了哇……

　　别人代码看多了可以用优先队列的东西都用上set了。

#include<set>

#include<cstdio>

#include<algorithm>

#define mp make_pair

#define pi pair

#define fi first

#define se second

#define MN 4000001

using namespace std;

int T,n,m,ne[MN],ma[MN],a,mmh;

set<pi<int,int> > s;

int main(){

    scanf("%d",&T);

    while (T--){

        s.clear();

        scanf("%d",&n);mmh=;

        for (int i=;i<=n;i++){

            scanf("%d",&a);

            ma[i]=ma[n+i]=a;

            ne[i]=i+;ne[n+i]=n+i+;s.insert(mp(a,i));s.insert(mp(a,i+n));

        }

        while (s.size()){

            pi<int,int> k=*s.begin();s.erase(s.begin());

            int w=ne[k.se];

            if (w<=*n&&ne[w]-k.se<=n&&k.fi==ma[w])

            ma[k.se]++,ne[k.se]=ne[w],s.insert(mp(ma[k.se],k.se));

        }

        for (int i=;i<=n+n;i++) if (ma[i]>mmh) mmh=ma[i];

        printf("%d\n",mmh);

    }

}