POJ 1037 DP

 
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
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]=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]=t) ++ans[i];  
              
        printf("%lld",ans[n]);  
        for(int i=n-1;i>=1;--i)  
            printf(" %lld",ans[i]);  
        puts("");  
    }  
    return 0;  
}  

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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]=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]=t) ++ans[i];
            
        printf("%lld",ans[n]);
        for(int i=n-1;i>=1;--i)
            printf(" %lld",ans[i]);
        puts("");
    }
    return 0;
}