POJ 1037 DP

 
#include <iostream>   
#include <cstdio>   
#include <cmath>   
#include <cstdlib>   
#include <string>   
#include <cstring>   
#include <algorithm>   
#include <iomanip>   
using namespace std;  
  
long long up[25][25];  
long long down[25][25];  
long long ans[25];  
  
void getfirst(long long n,long long c,bool u){  
    if(n==0) return ;  
    long long sum=0,t;  
    if(!u) { //前一步是up,當前步要down   
        t=ans[n+1];  
        while(sum+down[n][t]<c)  
            sum+=down[n][t++];  
    } else { //前一步是down,當前步要up   
        t=1;  
        while(sum+up[n][t]<c)  
            sum+=up[n][t++];  
    }  
    ans[n]=t;  //定位   
    getfirst(n-1,c-sum,!u);  //搜索下一位   
    for(int i=1;i<n;++i)  
        if(ans[i]>=t) ++ans[i];  
}  
  
void Init(){  
    up[1][1]=down[1][1]=1;  
    for(int i=2; i<=20; ++i)  
        for(int j=1; j<=i; ++j) {  
            up[i][j]=down[i][j]=0;  
            for(int k=j; k<=i-1; ++k)  
                up[i][j]+=down[i-1][k];  
            for(int k=1; k<=j-1; ++k)  
                down[i][j]+=up[i-1][k];  
        }  
}  
int main(){  
    Init();  
    int T; scanf("%d",&T);  
    while(T--){  
        long long c,n;  
        scanf("%lld%lld",&n,&c);   
          
        long long sum=0,t=1;  
        while(sum+up[n][t]+down[n][t]<c){  
            sum+=up[n][t]+down[n][t];  
            ++t;  
        }  
        ans[n]=t;  //定位首位   
        //搜索下一位   
        if(sum+down[n][t]<c)                      //在up中   
            getfirst(n-1,c-sum-down[n][t],false);  
        else                                      //在down中    
            getfirst(n-1,c-sum,true);  
        for(int i=1;i<n;++i)// 比如當n=5時, 第一個選了t=3, 還有1,2,4,5 後面會對應到1,2,3,4, 大於t的都相對-1, 最終要+1    
            if(ans[i]>=t) ++ans[i];  
              
        printf("%lld",ans[n]);  
        for(int i=n-1;i>=1;--i)  
            printf(" %lld",ans[i]);  
        puts("");  
    }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
using namespace std;

long long up[25][25];
long long down[25][25];
long long ans[25];

void getfirst(long long n,long long c,bool u){
    if(n==0) return ;
    long long sum=0,t;
    if(!u) { //前一步是up,當前步要down
        t=ans[n+1];
        while(sum+down[n][t]<c)
            sum+=down[n][t++];
    } else { //前一步是down,當前步要up
        t=1;
        while(sum+up[n][t]<c)
            sum+=up[n][t++];
    }
    ans[n]=t;  //定位
    getfirst(n-1,c-sum,!u);  //搜索下一位
    for(int i=1;i<n;++i)
        if(ans[i]>=t) ++ans[i];
}

void Init(){
    up[1][1]=down[1][1]=1;
    for(int i=2; i<=20; ++i)
        for(int j=1; j<=i; ++j) {
            up[i][j]=down[i][j]=0;
            for(int k=j; k<=i-1; ++k)
                up[i][j]+=down[i-1][k];
            for(int k=1; k<=j-1; ++k)
                down[i][j]+=up[i-1][k];
        }
}
int main(){
    Init();
    int T; scanf("%d",&T);
    while(T--){
        long long c,n;
        scanf("%lld%lld",&n,&c); 
        
        long long sum=0,t=1;
        while(sum+up[n][t]+down[n][t]<c){
            sum+=up[n][t]+down[n][t];
            ++t;
        }
        ans[n]=t;  //定位首位
        //搜索下一位
        if(sum+down[n][t]<c)                      //在up中
            getfirst(n-1,c-sum-down[n][t],false);
        else                                      //在down中 
            getfirst(n-1,c-sum,true);
        for(int i=1;i<n;++i)// 比如當n=5時, 第一個選了t=3, 還有1,2,4,5 後面會對應到1,2,3,4, 大於t的都相對-1, 最終要+1 
            if(ans[i]>=t) ++ans[i];
            
        printf("%lld",ans[n]);
        for(int i=n-1;i>=1;--i)
            printf(" %lld",ans[i]);
        puts("");
    }
    return 0;
}