//up[i][j]表示：长度为i的fence以第j高的木条开始，使前两根木条呈上升的fence总数
//down[i][j]同理。

#include<stdio.h>
#define GetMax(a,b) ((a)>(b)?(a):(b))

int k,i,j,maxn;
__int64 up[21][21],down[21][21],c[101],n[101];

void generate(int n,__int64 c)
{
	int i,j,find,fup,s[21];
	for(i=1;i<=n;++i) s[i]=i;
	for(i=n;i>=1;--i){
		if(i==n){//第一根木条单独处理，因为可能是上升也可能是下降的
			for(j=1;j<=i;++j){
				if(c-down[i][j]<=0) {find=j;fup=1;break;}
				else c-=down[i][j];
				if(c-up[i][j]<=0) {find=j;fup=0;break;}
				else c-=up[i][j];
			}
			printf("%d ",s[find]);
			for(j=find;j<=i;++j) s[j]=s[j+1];
		}
		else
			if(fup==1){
				for(j=1;j<find;++j)
					if(c-up[i][j]<=0) {find=j;fup=0;break;}
					else c-=up[i][j];
				printf("%d ",s[find]);
				for(j=find;j<=i;++j) s[j]=s[j+1];
			}
			else{
				for(j=find;j<=i;++j)
					if(c-down[i][j]<=0) {find=j;fup=1;break;}
					else c-=down[i][j];
				printf("%d ",s[find]);
				for(j=find;j<=i;++j) s[j]=s[j+1];
			}
	}
	printf("\n");
}

int main() 
{ 
	scanf("%d",&k);
	maxn=0;
	for(i=1;i<=k;++i){
		scanf("%d %I64d",&n[i],&c[i]);
		maxn=GetMax(maxn,n[i]);
	}
	
	//DP
	up[1][1]=down[1][1]=1;
	for(i=2;i<=maxn;++i){
		for(j=2;j<=i;++j)
			down[i][j]=down[i][j-1]+up[i-1][j-1];
		for(j=1;j<=i;++j) up[i][j]=down[i][i-j+1];
	}

	for(i=1;i<=k;++i) generate(n[i],c[i]);
	return 0; 
}

• Re:终于过了。。。。。我怎么理解地这么慢呢。。。 (13) yzthz 2010-01-14 23:26:41
  • Re:终于过了。。。。。我怎么理解地这么慢呢。。。 (9) morenan 2010-09-29 08:47:36