CF9D How many trees?
D e s c r i p t i o n Description Description
n n n 개의 노드 높이가 h h h인 두 갈래 나무의 개수를 구하다
h ≤ n ≤ 35 h\leq n\leq 35 h≤n≤35
S o l u t i o n Solution Solution
f[i][j] f[i][j] f[i][j]는 ii의 결점을 나타내고 높이는 ≤j\leqj≤j의 두 갈래 나무 개수를 나타낸다.
분명: f [0] [i] = 1 f [0] [i] = 1 f [0] [i] = 1
f [ i ] [ j ] = ∑ f [ l s o n ] [ j − 1 ] × f [ r s o n ] [ j − 1 ] f[i][j]=\sum f[lson][j-1]\times f[rson][j-1] f[i][j]=∑f[lson][j−1]×f[rson][j−1]
분명히 우리는 왼쪽 나무의 개수를 확정하면 오른쪽 나무의 개수를 확정할 수 있다. 매거 kk는 왼쪽 나무 노드의 개수이다. 그러면
f [ i ] [ j ] = ∑ k = 0 i − 1 f [ k ] [ j − 1 ] × f [ i − k − 1 ] [ j − 1 ] f[i][j]=\sum_{k=0}^{i-1}f[k][j-1]\times f[i-k-1][j-1] f[i][j]=∑k=0i−1f[k][j−1]×f[i−k−1][j−1]
답은 명백하다. f[n][n]−f[n][h−1] f[n][n]-f[n][h-1] f[n]−f[n][n][h−1]
그리고 w o r k o u t work\out work out입니다.
시간 복잡도: O(n 3) O(n^3) O(n3)
C o d e Code Code
#include
using namespace std;long long f[36][36];int n,h;
signed main()
{
scanf("%d%d",&n,&h);
for(register int i=0;i<=n;i++) f[0][i]=1;
for(register int j=1;j<=n;j++)
for(register int i=1;i<=n;i++)
for(register int k=0;k<i;k++)
f[i][j]+=f[k][j-1]*f[i-k-1][j-1];
printf("%lld",f[n][n]-f[n][h-1]);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.