Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 2824: [AHOI2012]铁盘整理

题目链接

由于一些原因 bzoj的这道题有毒
所以我放上luogu的题目链接吧
传送门

题目描述


输入输出格式

输入格式:

共两行。第一行为铁盘个数N(1<=N<=50),第二行为N个不同的正整数,分别为从上到下的铁盘的半径R。(1<=R<=100)

输出格式:

一个正整数,表示使铁盘从小到大有序需要的最少翻转次数。

输入输出样例

输入样例#1: 复制

5
2 4 3 5 1

输出样例#1: 复制

5

想说的话

这题bzoj据说是加强了数据
然后我的A*就被卡出了x
显然luogu没有这个鬼问题

题解I

先说说A*做法
构造那个估值函数怎么构造呢
我们考虑最终的状态 相邻两个的差绝对值都为1
就用这个性质来构造函数
然后具体怎么判断是不是已经结束了呢
我们可以用a[1]和a[2]的大小来判断
如果a[1]小 那么就是最终情况
否则就是翻转一次到达最终情况
接着dfs就行了
用一个ans来记录当前翻转了多少次
能达成目标的时候就停下来
就结束了

代码I

题解II

大体的思路差不太多
都是利用了最终状态的性质
然后这个方法就是剪枝+剪枝+剪枝
各种无脑剪枝
然后就在bzoj上面过了
从本质来讲跟第一种A*并没与什么本质上的区别
直接上代码了

代码II

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏