首页 > 代码库 > 51nod 1412 AVL数的种类(DP
51nod 1412 AVL数的种类(DP
题意给了n个节点的AVL数 问种类
树的深度不大
那么转移方程很明显了
dp[i][j] 代表的是节点为n深度为j的树的种类
k为左子树的节点个数
//dp[i][j+1] += dp[k][j]*dp[i-k-1][j];
//dp[i][j+1] += 2*dp[k][j-1]*dp[i-k-1][j];
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> using namespace std; const long long MOD = 1000000007; typedef long long ll; ll dp[2100][30];//i 表示个数 j表示深度 ll check(int x,int y) { return 0; } void init() { dp[0][0] = dp[1][1] = 1; //dp[i][j+1] += dp[k][j]*dp[i-k-1][j]; //dp[i][j+1] += 2*dp[k][j-1]*dp[i-k-1][j]; for(int i=2;i<=2000;i++) { for(int j=0;j<=17;j++) { for(int k=0;k<i;k++) { dp[i][j+1] += dp[k][j]*dp[i-k-1][j]; dp[i][j+1] += 2*dp[k][j-1]*dp[i-k-1][j]; dp[i][j+1]%=MOD; } } } } int main() { // 0 0 // 1 1 // 2 2 // 3 init(); int n; cin>>n; ll ans = 0; for(int i=0;i<30;i++) { ans += dp[n][i]; } cout<<ans%MOD<<endl; return 0; }
51nod 1412 AVL数的种类(DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。