当前位置： 首页 > news >正文

【动态规划】P12223 [蓝桥杯 2023 国 Java B] 非对称二叉树|普及+

news 2025/5/25 11:38:18

本文涉及知识点

C++动态规划

P12223 [蓝桥杯 2023 国 Java B] 非对称二叉树

题目描述

小明觉得不对称的东西有着独特的美感。

对于一棵含有 n n n 个结点的二叉树，小明规定如果对于其中任意一个结点 i i i 都满足条件： max ⁡ { h l i , h r i } ≥ k × min ⁡ { h l i , h r i } \max \{h_{l_i}, h_{r_i}\} \geq k \times \min \{h_{l_i}, h_{r_i}\} max{hli​​,hri​​}≥k×min{hli​​,hri​​} 则此二叉树为一棵非对称二叉树。其中 l i , r i l_i, r_i li​,ri​ 分别为 i i i 的左儿子和右儿子， h x h_x hx​ 表示以 x x x 为根的子树的高度（如果结点 x x x 不存在则视为高度等于 0 0 0）。

给定 n , k n, k n,k，计算有多少棵不同的非对称二叉树。

输入格式

输入共 1 1 1 行，两个正整数 n n n、 k k k。

输出格式

输出共 1 1 1 行，一个整数。

输入输出样例 #1

输入 #1

4 2

输出 #1

12

说明/提示

样例说明

所有 12 12 12 种情况如下：

评测用例规模与约定

  • 对于 20 % 20\% 20% 的数据，保证 n ≤ 12 n \leq 12 n≤12。
  • 对于 100 % 100\% 100% 的数据，保证 n ≤ 35 n \leq 35 n≤35， 1 ≤ k ≤ n 1 \leq k \leq n 1≤k≤n。

动态规划

动态规划的状态表示

dp[n][leve]表示 n个节点，最大层次是leve的非对称二叉树方案数。 n ∈ [ 0 , N − 1 ] , 0 ≤ l e v e ≤ n n\in[0,N-1],0 \leq leve \leq n n∈[0,N−1],0≤leve≤n。空间复杂度：O(NN)。

动态规划的填报顺序

枚举后继状态,n从1到N,leve从1到n。

动态规划的转移方程

每种后继状态，枚举其左、右节点的数量n1,n-1-n1，及左右节点的层次leve1、leve2。
如果 m a x ( l e v e 1 , l e v e 2 ) + 1 ≠ l e v e max(leve1,leve2)+1\neq leve max(leve1,leve2)+1=leve忽略， d p [ n ] [ l e v e ] + = d p [ n 1 ] [ l e v e 1 ] × d p [ n − 1 − n 1 ] [ l e v e 2 ] dp[n][leve] += dp[n1][leve1] \times dp[n-1-n1][leve2] dp[n][leve]+=dp[n1][leve1]×dp[n−1−n1][leve2]
如果对称，忽略。
时间复杂度： O ( n 5 ) O(n^5) O(n5)，可以只枚举leve1或leve2等于leve-1，这样时间复杂度 O ( n 4 ) O(n^4) O(n4) leve1和leve2都等于leve-1，不要重复枚举。

动态规划的初始值

dp[0][0]=1，其它全部0。

动态规划的返回值

∑ d p . b a c k ( ) \sum dp.back() ∑dp.back()
注意： 可能会溢出，我们试试 n=35,k=1 。但测试数据不会溢出。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T1, class T2, class T3, class T4, class T5, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5,T6,T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class Solution {
public:long long Ans(int N, int K) {vector<vector<long long>> dp(N + 1, vector<long long>(N + 1));dp[0][0] = 1;for (int n = 1; n <= N; n++) {for (int leve = 1; leve <= n; leve++) {for (int n1 = 0; n1 < n; n1++) {const int n2 = n - 1 - n1;for (int leve1 = 0; leve1 <= min(n1, leve - 1); leve1++) {for (int leve2 = 0; leve2 <= min(n2, leve - 1); leve2++) {if (max(leve1, leve2) + 1 != leve) { continue; }if (max(leve1, leve2) >= K * min(leve1, leve2)) {dp[n][leve] += dp[n1][leve1] * dp[n2][leve2];//assert(dp[n][leve] <= 2e9);}}}}}}long long ans = accumulate(dp.back().begin(), dp.back().end(), 0LL);return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob;int N,K;cin >> N >> K  ;
#ifdef _DEBUG	printf("N=%d,K=%d", N,K);//Out(W, ",W=");//Out(edge, ",edge=");Out(grid, ",grid=");//Out(a, ",a=");Out(rr, ",rr=");//  //Out(ab, ",ab=");//  //Out(par, "par=");//  //Out(que, "que=");//  //Out(B, "B=");
#endif // DEBUG	auto res = Solution().Ans(N,K);	cout << res;return 0;
};

单元测试

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T1, class T2, class T3, class T4, class T5, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5,T6,T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class Solution {
public:long long Ans(int N, int K) {vector<vector<long long>> dp(N + 1, vector<long long>(N + 1));dp[0][0] = 1;for (int n = 1; n <= N; n++) {for (int leve = 1; leve <= n; leve++) {for (int n1 = 0; n1 < n; n1++) {const int n2 = n - 1 - n1;for (int leve1 = 0; leve1 <= min(n1, leve - 1); leve1++) {for (int leve2 = 0; leve2 <= min(n2, leve - 1); leve2++) {if (max(leve1, leve2) + 1 != leve) { continue; }if (max(leve1, leve2) >= K * min(leve1, leve2)) {dp[n][leve] += dp[n1][leve1] * dp[n2][leve2];//assert(dp[n][leve] <= 2e9);}}}}}}long long ans = accumulate(dp.back().begin(), dp.back().end(), 0LL);return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob;int N,K;cin >> N >> K  ;
#ifdef _DEBUG	printf("N=%d,K=%d", N,K);//Out(W, ",W=");//Out(edge, ",edge=");Out(grid, ",grid=");//Out(a, ",a=");Out(rr, ",rr=");//  //Out(ab, ",ab=");//  //Out(par, "par=");//  //Out(que, "que=");//  //Out(B, "B=");
#endif // DEBUG	auto res = Solution().Ans(N,K);	cout << res;return 0;
};

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

http://www.xdnf.cn/news/629317.html

相关文章：

  • python打卡day35@浙大疏锦行
  • 【笔记】OpenCV的学习（未完）
  • CodeBuddy 实现图片转素描手绘工具
  • springboot中各模块间实现bean之间互相调用（service以及自定义的bean）
  • 符合Python风格的对象(使用 __slots__ 类属性节省空间)
  • 搜索二叉树
  • 开盘啦 APP 抓包 逆向分析
  • 从有线到无线：PLC通讯“剪断“最后一根线！
  • MQTT-排它订阅
  • STM32F103 HAL多实例通用USART驱动 - 高效DMA+RingBuffer方案，量产级工程模板
  • python训练营第33天
  • Lesson 22 A glass envelope
  • HJ14 字符串排序【牛客网】
  • Spring AI 源码解析：Tool Calling链路调用流程及示例
  • 从法律视角看债务管理：湖北理元理律师事务所的实践探索
  • 【信息系统项目管理师】一文掌握高项常考题型-成本类计算
  • 巡礼中国西极·跨越昆仑天山 | 北斗卫星徽章护航昆仑科考
  • 神经算子项目实战：数据分析、可视化与实现全过程
  • 归一化 超全总结！！
  • leetcode hot100刷题日记——16.全排列
  • 探秘Transformer系列之（34）--- 量化基础
  • 开源轻量级语音合成和语音克隆模型：OuteTTS-1.0-0.6B
  • AWTK嵌入式图形框架开发备忘(二)
  • 【GESP真题解析】第 5 集 GESP 二级 2023 年 3 月编程题 2：百鸡问题
  • 【Python】【电网规划】基于经济与可靠性双目标的混合配电系统规划及可靠性评估
  • ShenNiusModularity项目源码学习（30：ShenNius.Admin.Mvc项目分析-15）
  • 可增添功能的鼠标右键优化工具
  • 【PINN】DeepXDE学习训练营(33)——pinn_forward-fractional_Poisson_1d.py
  • C++：共享指针unique_ptr的理解与应用
  • 每日定投40刀BTC（17）20250511 - 20250524