UVa10128

UVa10128

dp [ 誰を使った ] [ これまでで最も高い身長 ] [ 前から見て何人見えるか ]

最も身長の高い人より後ろに並んでいる人は当然見えない。
つまり、その人の前と後ろで分けて考えることが出来る。

#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <vector>

#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;
#define LOG()  cout << __LINE__ << ", " << __func__ << endl;

typedef long long int lli;

using namespace std;

const int N = 13;
const int BIT = 1 << N;
lli dp[BIT][N][N];

int main(int argc, char *argv[])
{
  fill(&dp[0][0][0], &dp[BIT - 1][N - 1][N], 0LL);

  dp[0][0][0] = 1;
  for (int bit = 0; bit < BIT; ++bit) {
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        for (int k = 1; k < N; ++k) {
          int b = 1 << (k - 1);
          if (bit & b) continue;
          dp[bit | b][max(i, k)][j + (i < k)] += dp[bit][i][j];
        }
      }
    }
  }

  int tc;
  cin >> tc;
  while (tc--) {
    int n, p, r;
    cin >> n >> p >> r;

    lli sum = 0;
    const int B = 1 << (n - 1);
    for (int bit = 0; bit < B; ++bit) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          sum += dp[bit][i][p - 1] * dp[bit ^ (B - 1)][j][r - 1];
        }
      }
    }

    cout << sum << endl;
  }

  return 0;
}