翻币问题
Description
有N个硬币(6<=N<=20000)全部正面朝上排成一排，每次将其中5个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。试编程找出步数最少的翻法，输出最少步数及翻法。
Input
从键盘输入一个正整数N(6<=N<=20000)，表示硬币的数量。
Output
第1行：一个整数，表示最少步数
第2行至最后一行：先是一个整数，表示步骤序号（从0开始编号），后接一个":"，再接当前硬币的状态（用一个整数表示正面朝上的硬币的个数）
Sample Input
6 (开始:6个硬币正面朝上)
Sample Output
0:6 (第0步结果:6个硬币正面朝上)
1:1 (第1步结果:1个硬币正面朝上)
2:4 (第2步结果:4个硬币正面朝上)
3:3 (第3步结果:3个硬币正面朝上)
4:2 (第4步结果:2个硬币正面朝上)
5:5 (第5步结果:5个硬币正面朝上)
6:0 (第6步结果:0个硬币正面朝上)
6 (最少用6步实现全部反面朝上)
Hint
只输出最少次数,其变化过程仅作参考
分析
这题我们可以用广搜来做
找出最短的全部硬币正面朝上的次数，也就是最优化问题
但是，为了避免重复，要记录好每次正面朝上的硬币的个数，是否已经出现过
#include<iostream>
using namespace std;
int tail,head,st1[200005],st2[200005],st3[200005],n,b[2000005];
void bfs()
{
tail=1;
st1[1]=n;st2[1]=0;//初始值，正面朝上n个，反面0个
b[n]=1;//当前已经出现过
do
{
head++;
for(int i=0;i<=5;i++)//遍历6种情况
if(st1[head]>=i&&st2[head]>=5-i)//条件
{
tail++;
st1[tail]=st1[head]-i+5-i;//正面朝上规律
st2[tail]=n-st1[tail];//反面朝上规律
st3[tail]=st3[head]+1;//由父节点过来，所以父节点加1
if(b[st1[tail]]==1)tail--;//已经出现过就不要它
b[st1[tail]]=1;
if(st1[tail]==0)
{
cout<<st3[tail];
return;
}
}
}while(head<=tail);
}
int main()
{
cin>>n;
bfs();
}
京公网安备 11010502036488号