找零钱、点移位 数的层次遍列法.txt

ACM资料大集合

#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

//找零钱问题 点移位问题 树的层次遍列法
/*
输入：
15 0

输出：
3

解释：
初始状态为15，结束状态为0
15=5+5+5  3个硬币
15=11+1+1+1  4个硬币
*/

int visited[30000];
#define MAX 100002
#define RMBNUM 3
long end;
long start;
int cishu;
long queue[MAX*2];
int flag;
int mianzhi[3]={11,5,1};//零钱问题，各零钱的面值

void visit(long s,long qi,long qs)
{
	int qsnum,duan,i;
	if(s==end) return;
	if(visited[s]==0)
	{
		visited[s]=1;
		queue[qi++%MAX]=s;
		duan=qi;//duan表示每次层次遍列开始的断点
		while(qi!=qs)
		{
			qsnum=queue[qs++%MAX];//出队
			visited[qsnum]=1;
			if(qs==duan) {cishu++;flag=0;}//出队时遇到上一次的断点，次数加1，并将flag置为0，准备下一次再置断点
			
			//这个是找零钱的约束条件
			for(i=0;i<RMBNUM;i++)
			{
				if(visited[qsnum-mianzhi[i]]==0&&qsnum-mianzhi[i]>=0)
				{	
					s=qsnum-mianzhi[i];
					if(s==end) return;//到达终点
					visited[s]=1;
					queue[qi++%MAX]=s;//入队
					if(flag==0) {duan=qi;flag=1;}//队里已无断点，置新的断点
				}
			}
/*			//这个是点移位的约束条件
			if(visited[qsnum-1]==0&&qsnum-1>=0) 
			{
				s=qsnum-1;
				if(s==end) return;
				visited[s]=1;
				queue[qi++%MAX]=s;
				if(flag==0) {duan=qi;flag=1;}
			}
			if(visited[qsnum+1]==0&&qsnum+1<=200002) 
			{
				s=qsnum+1;
				if(s==end) return;
				visited[s]=1;
				queue[qi++%MAX]=s;
				if(flag==0) {duan=qi;flag=1;}
			}
			if(visited[qsnum*2]==0&&qsnum*2<=200002)
			{
				s=qsnum*2;
				if(s==end) return;
				visited[s]=1;
				queue[qi++%MAX]=s;
				if(flag==0) {duan=qi;flag=1;}
			}
*/		}
	}
}


int main()
{
	long s;
	scanf("%d%d",&start,&end);
	s=start;
	cishu=0;
	visit(s,0,0);
	printf("%d\n",cishu);
	return 0;
}