codechef [snackdown2017 Onsite Final] Fusing Weapons

发布时间:2017-7-9 7:36:08编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"codechef [snackdown2017 Onsite Final] Fusing Weapons ",主要涉及到codechef [snackdown2017 Onsite Final] Fusing Weapons 方面的内容,对于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 4000001using 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=0;        for (int i=1;i<=n;i++){            scanf("%d",&a);            ma[i]=ma[n+i]=a;            ne[i]=i+1;ne[n+i]=n+i+1;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<=2*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=1;i<=n+n;i++) if (ma[i]>mmh) mmh=ma[i];        printf("%d\n",mmh);    }}
View Code


上一篇:C#接口的三种实现方式

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款