PKU 1037-A decorative fence

問題概要

長さが1〜Nの木がそれぞれあり、それを使って柵を作りたい。
ただし、柵はジグザグな形になるようにするようにしたい。
C番目の作り方を求めよ。

解法

dp[進行方向の残りの木の本数][全体の残りの木の本数]とすることで、O(N^2)でパターン数を求めることが出来る。
パターン数から作り方を復元する。

実装(C++)

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long lli;
int N;
lli C;

bool input(){
  static int testcase=-1;
  if(testcase<0){
    cin>>testcase;
  }
  if(testcase==0)return false;
  cin>>N>>C;
  C--;
  testcase--;
  return true;
}
lli dp[30][30];
// forward：進行方向の数、n；全体の残りの数)
lli solve(int forward,int n){
  if(dp[forward][n]>=0)return dp[forward][n];
  if(n==0)return 1;
  lli sum=0;
  for(int i=0;i<forward;i++){
    sum+=solve(i+n-forward,n-1);
  }
  return dp[forward][n]=sum;
}
int main(){
  memset(dp,-1,sizeof(dp));
  while(input()){
    int s=0,b;
    for(int i=1;i<=N;i++){ //最初の数を決める
      if(C<solve(i-1,N-1)){
        b=-1;
        s=i;
        break;
      }else{
        C-=solve(i-1,N-1);
      } 
      if(C<solve(N-i,N-1)){
        b=1;
        s=i;
        break;
      }else{
        C-=solve(N-i,N-1);
      }
    }
    bool used[21];
    memset(used,0,sizeof(used));
    used[s]=true;
    cout<<s;
    int back=s;
    for(int i=1;i<N;i++){
      if(b==1){
        int cnt=0;
        for(int j=1;j<back;j++){
          if(used[j]==false)cnt++;
        }
        for(int j=back+1;j<=N;j++){
          if(used[j])continue;
          if(C<solve(cnt,N-i-1)){
            cout<<" "<<j;
            back=j;
            used[j]=true;
            break;
          }else{
            C-=solve(cnt,N-i-1);
          }
          cnt++;
        }
      }else{
        int cnt=0;
        for(int j=1;j<=N;j++){
          if(used[j]==false)cnt++;
        }
        for(int j=1;j<back;j++){
          if(used[j])continue;
          cnt--;
          if(C<solve(cnt,N-i-1)){
            cout<<" "<<j;
            back=j;
            used[j]=true;
            break;
          }else{
            C-=solve(cnt,N-i-1);
          }
        }
      }
      b=b*-1;
    }
    cout<<endl;
  }
}