事先预警：由于我太蒻了，本做法只能在POJ、LOJ等小数据（N<=100）平台上通过,在UVa(洛谷)上大数据并不能通过

戳我获得更好的观看效果

本题不用看，爆搜就是了，但是纯爆搜显然会爆时间，所以要加上一些剪枝

我们来看一下一些常用的剪枝（什么剪枝，其实这么多枝砍掉了，树都没了）

1.最优化剪枝：不存在的，本题求输出方案

2.优化搜索顺序：由于是SPJ，我们对于每个位置上的数字倒着枚举，容易搜索到答案

3.可行性剪枝：需用到数学方法，但是我不会，由于不加该剪枝也能过，所以不讲

最重要的：卡常

剩下的思路见代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

inline int read(){

	char chr = getchar();	int f = 1,ans = 0;

	while(!isdigit(chr)) {if(chr == '-') f = -1;chr = getchar();}

	while(isdigit(chr))  {ans = (ans << 3) + (ans << 1);ans += chr - '0';chr = getchar();}

	return ans* f ;

}

void write(int x){

	if(x < 0) putchar('-'),x = -x;

	if(x > 9) write(x / 10);

	putchar(x % 10 + '0');

}

int n,m;

int ff=0;

int a[50];

int book[500];

void dfs(int x,int m){//当前找到第n个数

	if(x==m+1){

		if(a[x-1]==n)//由于每个位置我们都用尽量大的数，第一次搜索到的就是答案

			ff=1;//标记答案找到了

		return;//返回

	}

	for(int i=n;i>=a[x-1]+1;i--){//枚举第x个位置的数值

		if(ff) return;

		int fff=0;

		for(int j=1;j<=x-1;j++){//判断能否由前面的数字构成

			if(i-a[j]>=1 && book[i-a[j]]){

				fff=1;

				break;

			}

		}

		if(fff){

			book[i]=1;

			a[x]=i;

			dfs(x+1,m);//往下搜

			book[i]=0;//回溯

			if(ff) return;

		}

	}

}

int main(){

	n=read();

	while(n!=0){

		if(n==1){

			write(1),puts("");

			n=read();

			continue;

		}

		ff=0;

		a[1]=1;

		book[1]=1;

		int i;

		for(i=2;i;i++){//枚举长度

			ff=0;

			memset(book,0,sizeof(book));//记录某个数是否搜索到过

			book[1]=1;//book[1]=1;

			dfs(2,i);

			if(ff)//退出

				break;

		}

		for(int j=1;j<=i;j++)

			write(a[j]),putchar(' ');

		puts("");

		n=read();

	}

	return 0;

}

巴特西

【POJ2248、LOJ#10021】 Addition Chains

事先预警：由于我太蒻了，本做法只能在POJ、LOJ等小数据（N<=100）平台上通过,在UVa(洛谷)上大数据并不能通过

戳我获得更好的观看效果

最重要的：卡常

最新文章

热门文章

巴特西

【POJ2248、LOJ#10021】 Addition Chains

事先预警：由于我太蒻了，本做法只能在POJ、LOJ等小数据（N<=100）平台上通过,在UVa(洛谷)上大数据并不能通过

戳我获得更好的观看效果

最重要的： 卡常

最新文章

热门文章

最重要的：卡常