Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
bfs,上限到199就可以了,因为对任一個合法的找钱序列,都可以改变顺序变成一個琐有部分和都小于200的序列#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator