G - 2-3 Trees (dp)
l 키 노드 를 포함 하 는 2, 3 나 무 는 모두 몇 가지 형태 가 있 는 지 구하 고 결과 에 대해 나머지 r 를 취한 다.
우 리 는 최 하층 (잎 노드) 의 개 수 를 알 기 때문에 우 리 는 위로 유도 할 수 있다. 이 n 개의 잎 은 몇 개의 2 아이의 아버지 노드 와 3 아이의 아버지 노드 를 구성 하고 한 층 한 층 위로 유도 할 수 있다.또한 각 층 의 2 자 부 노드 와 3 자 부 노드 의 배열 도 형태 가 다양한 원인 이다.
그래서 dp [n] = dp [n] + dfs (i + t) * c [i + t] [t]
dfs (i + t) 는 하위 노드 수가 i + t 의 종 류 를 나타 낸다.
c [i + t] [t] 는 조합 수 로 i + t 에서 t 개 를 꺼 내 는 방법 개수 입 니 다.
#include
#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
ll n,mod;
ll dp[5005];
ll c[2505][2505];
void init()
{
c[0][0]=1;
c[1][0]=1;
c[1][1]=1;
for(int i=2;i<=n/2;i++)
{
c[i][0]=c[i][i]=1;
for(int j=1;j>n>>mod)
{
init();
memset(dp,0,sizeof(dp));
dp[0]=1;
dp[1]=1;
dp[2]=1;
dp[3]=1;
printf("%lld
",dfs(n));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 1000 개 노크 #2. Longest common substringsProblem Solution DP (다이나믹 프로그래밍) 중에서 고전적인 문제입니다. 두 문자열을 S1과 S2, 각각의 길이를 M, N으로 설정합니다. 총당으로 S1에서 모든 부분 문자열을 추출하고, 그것들이 S2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
