프양연 Pole / DP

1. 디피 관계식 만들기 2. 기준을 제일 작은 막대의 왼쪽, 사이, 오른쪽으로 둠 3. 디피 3차원 배열 만듦

#include <stdio.h> #define MAXN 21 long long D[MAXN][MAXN][MAXN]; int main() { int t, TestCase; int N, L, R; int i, l, r; D[1][1][1] = 1; D[2][1][2] = D[2][2][1] = 1; for (i = 3; i < MAXN; i++) { for (l = 1; l < MAXN; l++) { for (r = 1; r < MAXN; r++) { //printf("%d %d %d\n", i, l, r); D[i][l][r] = D[i - 1][l - 1][r] + (i - 2)*D[i - 1][l][r] + D[i - 1][l][r - 1]; } } } freopen("input.txt","r",stdin); scanf("%d", &TestCase); for (t = 1; t <= TestCase; t++) { scanf("%d %d %d", &N, &L, &R); //D(N,L,R)경우의 수를 구하자 //1. 가장짧은 막대기가 가장 왼쪽에 있을 경우 //D(N-1, L-1, R) //2. 사이에 있을 경우 //(N-2)*D(N-1, L, R) //3. 오른쪽에 있을 경우 //D(N-1, L, R-1); //기저사례 //D(2,1,2) = D(2,2,1) = 1 printf("#%d %lld\n", t, D[N][L][R]); } return 0; }