?? 找零錢、點移位 數(shù)的層次遍列法.txt
字號:
#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;
//找零錢問題 點移位問題 樹的層次遍列法
/*
輸入:
15 0
輸出:
3
解釋:
初始狀態(tài)為15,結束狀態(tài)為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;}//出隊時遇到上一次的斷點,次數(shù)加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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -