Sunnypig闯三角关

背景

贪玩的sunnypig请Charles为他打造一个奇幻世界，Charles欣然答应了。然而一向善于出难题的Charles是决不会轻易让sunnypig轻松拥有一个奇幻世界的，于是Charles在建造过程中设置了重重机关，只有在sunnypig破解了这些障碍之后，才能尝试到奇幻世界中最有玩头的终极宝贝——时空穿梭机。虽然奇幻世界中其他的宝贝也很有趣，但贪玩的sunnypig怎能放过打boss的机会呢？于是他开始了破解障碍的旅程。

描述

第二道障碍来源于一种古老的数学发现——杨辉三角，不过应该是倒过来的杨辉三角。若给出1~n的一个排列A，则将A1、A2相加，A2、A3相加……An-1、An相加，则得到一组n-1个元素的数列B；再将B1、B2相加，B2、B3相加，Bn-2、Bn-1相加，则得到一组n-2个元素的数列……如此往复，最终会得出一个数T。而Charles给sunnypig出的难题便是，给出n和T，再尽可能短的时间内，找到能通过上述操作得到T且字典序最小的1~n的排列。经过汉诺塔问题的训练，sunnypig开始沉着的思考。。。

格式

输入格式

本题有多组数据，对于每组数据：
一行两个整数n（0<n<=20），t即最后求出来的数。

用文件结尾符判断输入结束。

输出格式

对于每组测试数据输出一行n个整数，用空格分开，行尾无多余空格，表示求出来的满足要求的1~n的一个排列。

样例1

样例输入1

4 16
3 9

样例输出1

3 1 2 4
1 3 2

限制

各个测试点2s
不同测试点分数可能不同

建立一个数组b[i][j][k],表示杨辉三角第i行从第j个数第k小的数，比如第4行，1 3 3 1,则b[4][1][1]=1,b[4][1][2]=1;b[4][1][3]=3;b[4][2][1]=1;b[4][2][2]=3;b[4][2][3]=3

搜索剪枝：每次搜索时判断剩余的数和剩余的杨辉数相乘的最小值和最大值，如果最小值加上当前和>T则剪枝，如果最大值加上当前和<T则剪枝

数据太弱了，可以找到大量的算不出来的数据比如 n=20 T=5904462 6143311

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 
 5 int n,t,a[25][25]={0},b[25][25][25];
 6 struct{int x,y;}order[25][25],tr;
 7 bool over=0;
 8 
 9 void search(int x,int sum,int ans[],bool vis[]){
10      if(over) return ;
11      if(x>n)
12      {
13        for(int i=1;i<n;++i) cout<<ans[i]<<" ";
14        cout<<ans[n]<<endl;
15        over=1;
16        return ;
17             }
18             
19      int min=0,max=0,d=1;
20      for(int i=1;i<=n;++i)
21      if(vis[i]==0)
22      {max+=i*b[n][x][d];min+=i*b[n][x][n-x-d+2];d++;}
23      if(sum+min>t||sum+max<t) return ;
24      for(int i=1;i<=n;++i)
25      if(vis[i]==0)
26      {
27        vis[i]=1;
28        ans[x]=i;
29        search(x+1,sum+a[n][x]*i,ans,vis);
30        vis[i]=0;           
31              }
32 
33      }
34 
35 int main()
36 { 
37     for(int i=1;i<=20;++i)
38     for(int j=1;j<=i;++j)
39     {
40       if(j==1||j==i) a[i][j]=1;
41       else a[i][j]=a[i-1][j-1]+a[i-1][j];
42       order[i][j].x=a[i][j];
43       order[i][j].y=j;
44             }
45     
46 
47     
48     
49     for(int i=1;i<=20;++i)
50     for(int j=1;j<=i;++j)
51     for(int k=j+1;k<=i;++k)
52     if(order[i][j].x>order[i][k].x)
53     {tr=order[i][j];order[i][j]=order[i][k];order[i][k]=tr;}
54     else if(order[i][j].x==order[i][k].x&&(order[i][j].y>order[i][k].y))
55     {tr=order[i][j];order[i][j]=order[i][k];order[i][k]=tr;}
56     
57     
58     
59     for(int i=1;i<=20;++i)
60     for(int j=1;j<=i;++j)
61     for(int k=1;k<=i-j+1;++k)
62     {
63       int z;int tot=0;
64       for(z=1;z<=i&&tot<k;++z)
65       if(order[i][z].y>=j) tot++;
66       b[i][j][k]=order[i][z-1].x;
67             }
68     
69     while(cin>>n>>t)
70     {
71        over=0;
72        int ans[25]={0};   
73        bool vis[25]={0};
74        search(1,0,ans,vis);       
75           
76            }
77   //  system("pause"); 
78     }