Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

bfs,上限到199就可以了,因为对任一個合法的找钱序列,都可以改变顺序变成一個琐有部分和都小于200的序列

Posted by KatrineYang at 2016-09-01 22:56:47 on Problem 1252 and last updated at 2016-09-01 22:58:05
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;

bool inRange(int n){
	return n >= 0 && n <= 199;
}

int main() {
	int N;
	cin >> N;
	for(int ii = 0; ii < N; ii++){
		int zsgs[200];
		for(int i = 1; i < 200; i++)zsgs[i] = -1;
		zsgs[0] = 0;
		queue<int> kydme;
		kydme.push(0);
		int me[6];
		for(int i = 0; i < 6; i++) cin >> me[i];
		int yjsclldgs = 0;
		int zd = 0;
		int zs = 0;
		while(!kydme.empty()){
			int top = kydme.front();
			kydme.pop();
			int cs = zsgs[top];
			for(int i = 0; i < 6; i++){
				int tar = top+me[i];
				if(!inRange(tar) || zsgs[tar] != -1){
					continue;
				}
				zsgs[tar] = cs+1;
				if(tar <= 100 && tar > 0){
					yjsclldgs++;
					if(cs+1 > zd) zd = cs+1;
					zs += (cs+1);
					if(yjsclldgs == 100){
						goto done;
					}
				}
				kydme.push(tar);
			}
			for(int i = 0; i < 6; i++){
				int tar = top-me[i];
				if(!inRange(tar) || zsgs[tar] != -1){
					continue;
				}
				zsgs[tar] = cs+1;
				if(tar <= 100 && tar > 0){
					yjsclldgs++;
					if(cs+1 > zd) zd = cs+1;
					zs += (cs+1);
					if(yjsclldgs == 100){
						goto done;
					}
				}
				kydme.push(tar);
			}
		}
		done:
		double pj = zs / 100.0;
		printf("%.2lf %d\n", pj, zd);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator