P4044 [AHOI2014/JSOI2014]保龄球
zxtikes
·
·
题解
前言
当一个蒟蒻开始了今天的做题，欣喜地开启了一道题。经过几番思索之后，果断地开始写起了 模拟退火。
很显然，如果我们考虑动态规划，会发现状态很多，难以储存；如果我们考虑搜索，枚举每一个可能的序列，再计算出最大得分，复杂度是 O(n!)，很明显的 TLE 瞬间起飞。接下来思考其他的做法，都是一筹莫展。
最后还是选择我们的 模拟退火，模拟退火骗分就是好。
说明
接下来讲解一下模拟退火大概是什么东西。
模拟退火适用于具有连续性的函数，具体地讲，是适用于，将一个问题的解决方式进行细微改变，所得到的答案改变也不会非常大的问题。
模拟退火不一定能得到真正的最优解，但是可以得到一个函数的 局部最优解，所以我们进行模拟退火一般进行多次，从而得到多个局部最优解，这样子，我们得到全局最优解的概率就大大提升。
模拟退火所求函数一般不规则，但是具有一定连续性。
例如如下函数：
其中 A, B, C 都是一个局部最优解，但我们观察到，B 才是全局最优解，但是我们一次退火很难保证就很求到 B 这个答案，所以要多次退火，才会有更大的概率得到全局最优解。
通常，模拟退火有如下几个概念：
-
初始温度 T_0，表示最开始随机的范围大小。
-
终止温度 T_E，表示我们这次退火结束的温度。一般情况下 T_E \rightarrow 0 。
-
衰减系数 T_x， 0<T_x<1 表示每一次退火温度的衰减值。一般情况下 T_x>0.9 ，这样子才能保证所得到的答案足够精确，如果 T_x<0.9 ，那么所得到的答案就很难保证是最优解了，虽然退火本身就玄学。
-
概率 P ，表示我们从一个候补答案，更新为另一个候补答案的概率。其中，如果我们的新候补答案大于当前答案，那么概率 P=1 也就是一定会更新答案；否则，我们将以一定的概率来决定是否更新。一般情况下，这个概率为：P=e^{-\Delta/t} （题目要求求最大值），或者，P=e^{\Delta/t} （题目要求求最小值） ，其中 \Delta=new-now， new 表示新候补答案，now 表示当前答案，t 一般情况下会用来表示答案变化范围，普遍性取值为温度 T ，这样保证 0<P<1 ，并且 P 随着 \Delta 的改变而改变，具体改变是正相关还是负相关，与题目求是最大值还是最小值有关。
以上 T_x 主要决定了模拟退火的复杂度，T_x 越大，复杂度越低，所得到的答案的精确度越高。
经过个人测试，此题需要要求 T_x>0.94， 别问我怎么测出来的。
题目分析
在本题中，对于每个轮次，有三种情况：全中，补中，失误。我们需要将打出的所有轮次的顺序重新排列，使得得分最高。
其中，补中会使选手在下一轮中的第一次尝试的得分将会以双倍计入总分。失误的情况属于一般情况，不具有特殊性，所以不做处理。最重要的是全中的情况。全中会使选手在计算总分时，下一轮的得分将会被乘 2 计入总分，最需要 特殊处理 的是，当原来最后一轮次全中，我们在重新排列的时候，也需要最后一轮次是全中，因为这样子才会有奖励的轮次，需要进行的轮数和重排前所进行的轮数是一致的，才满足题意。
本题目中，我们用温度 T ，表示答案更新范围，当 T \rightarrow 0，也就是达到终止温度 T_E 时，我们就获得了一个候补答案。
最后我们进行多次退火就可以了。
什么？你说你不知道该进行多少次退火？不会计算复杂度？
这里有一个很方便的函数，可以帮助你卡着时间过，让你放心且愉悦。
while ((double)clock()/CLOCKS_PER_SEC<0.8)
如果你不喜欢用卡时，那么这个退火的次数一般进行 $1000 \sim 5000$ 次。
一般 $T_x$ 越大 ，这个次数可以适当低，但最好让次数多一些。
经过测试，当 $T_x=0.95$ 时，次数需要等于2000，只有90分，3000就可以成功 AC 。~~别问我怎么知道的~~。
所以还是卡时安心一些。
对于每次的新的答案，我们用函数 $\text{calc}$ 求出，求得方式与题意相同。
------------
## 代码展示
说了很多话，大家看的其实还是很抽象的，所以还是放代码，帮助大家理解一下实现的思路。
```cpp
#include<bits/stdc++.h>
#define ll long long
#define inf 1e9
#define rep(i,l,r) for(register int i=l;i<=r;++i)
#define per(i,r,l) for(register int i=r;i>=l;--i)
#define x first
#define y second
using namespace std;
const int N=55;
typedef pair<int,int> pii;
int n,m;
pii q[N];//pair 存储每一个轮次
int ans;
inline int calc(){//计算函数
int ret=0;
rep(i,1,m){
ret+=q[i].x+q[i].y;
if(i<=n){
if(q[i].x==10)ret+=q[i+1].x+q[i+1].y;//全中情况
else if(q[i].x+q[i].y==10)ret+=q[i+1].x;// 补中情况
}
}
ans=max(ans,ret);// 更新答案
return ret;
}
inline void simulate_anneal(){//模拟退火函数
// 初始温度T0 1e4 终止温度Te 1e-4 衰减系数Tx 0.97
for(double t=1e4;t>1e-4;t*=0.97){
int a=rand()%m+1,b=rand()%m+1;
int now=calc();
swap(q[a],q[b]);//得到下一个随机的情况
if(n+(q[n].x==10)==m){
int nxt=calc();//得到下一个答案的情况
int delta=nxt-now;//求答案改变量delta
if(exp(delta/t)<(double)rand()/RAND_MAX)swap(q[a],q[b]);//以一定的概率是否更新答案
}
else swap(q[a],q[b]);
}
}
int main(){
scanf("%d",&n);
rep(i,1,n)scanf("%d%d",&q[i].x,&q[i].y);
if(q[n].x==10)m=n+1,scanf("%d%d",&q[m].x,&q[m].y);//处理最后一轮次情况
else m=n;
while ((double)clock()/CLOCKS_PER_SEC<0.8)simulate_anneal();//卡时 模拟退火
printf("%d\n",ans);//输出答案
return 0;
}
```