#include<iostream>
#include<queue>
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXN 100001
struct node
{
	int data;
	int pre;
	int no;
}road[MAXN];
int ans[101],n;
void bfs(int n)
{
	queue<node>temp;
	node mid2;
	road[0].data=1;
	road[0].pre=-1;
	road[0].no=0;
	int k=1;
	bool flag=false;
	temp.push(road[0]);
	while(!temp.empty()&&!flag)
	{
		mid2=temp.front();
		temp.pop();
		if(mid2.data==n)
		{   
            next:
			int end=mid2.no,t=0;
			while(end!=-1)
			{
				ans[t++]=road[end].data;
				end=road[end].pre;
			}
			for(int i=t-1;i>=0;i--)
				printf("%d ",ans[i]);
			printf("\n");
			flag=true;
			return;
		}	
		int end=mid2.no;
		while(end!=-1&&!flag)
		{
			if(mid2.data+road[end].data<=n)
			{
				road[k].data=mid2.data+road[end].data;
				road[k].pre=mid2.no;
				road[k].no=k;
				temp.push(road[k]);
				k++;
			}
			if(road[k-1].data==n)
			{
				mid2=road[k-1];
				goto next;
			}
			end=road[end].pre;
		}
	}
}
int main()
{
	while(scanf("%d",&n)!=EOF&&n)
	{
		bfs(n);
	}
	return 0;
}

• 应该是没剪枝好 (0) twilight 2009-09-11 11:21:57
  • G++ 200多MS C++ TLE，我汗 (43) dynamic_study 2009-09-11 11:38:03
    • 我的经验是用STL的话C++(VC)会比G++快一点..... (0) twilight 2009-09-11 11:40:51
      • 哦 大牛发话我信了！ (0) dynamic_study 2009-09-11 12:14:50