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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

0ms 迭代,

Posted by yp0413170434 at 2019-03-15 12:54:28 on Problem 2248
#include<string>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
#pragma warning(disable:4996)
const int maxn = 110 + 10;
int road[maxn];
int ans[maxn];
bool vis[maxn];
int dex;
int n;

//int minn = 9999;
int Max;
int judge(int num)
{	
	int cnt = 0;
	while (num < n)
	{
		num *= 2;
		cnt++;
	}
	return cnt;
}
bool ida(int k)
{
	if (k > Max)
	{
		if (road[Max] == n)
			return true;
		else
			return false;
	}

	for (int i = k-1; i >=1; i--)
	{
		for (int j = k-1; j >=1 ;j--)
		{	
			//if (road[i] + road[j] <= road[k - 1])
			//	break;
			if (road[i]+road[j]<=n&&!vis[road[i]+road[j]])
			{	
				if (judge(road[i] + road[j])+k > Max)
					return false;
				vis[road[i]+road[j]] = true;
				road[k] = road[i] + road[j];
				if (ida(k + 1))
					return true;
				vis[road[i] + road[j]] = false;
				//return true;
			}
		}
	}
	return false;
}
int main()
{
	road[1] = 1;
	while (scanf("%d",&n),n)
	{
		if (n == 1)
		{
			cout << 1 << endl;
			continue;
		}
		/*if (n == 2)
		{
			cout << 2 << endl;
			continue;
		}*/
		for (Max = 2; ; Max++)
		{
			memset(vis, false, sizeof vis);
			if (ida(2))
			{	
				
				for (int i = 1; i <= Max; i++)
				{
					if (i!=1)
						printf(" ");	
					printf("%d", road[i]);
				}
				//memcpy(ans, road, sizeof road);
				break;
			}
		}
//		if (n == 1)
	//		cout << 1;
		//else
	
		cout<< endl;
	}
	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