【算法竞赛进阶指南】金字塔(区间DP+dfs序)

简介: 【算法竞赛进阶指南】金字塔(区间DP+dfs序)

原题链接


题意:


给定序列表示dfs一棵树遍历得到的顺序,每次经过一个节点都输出该节点对应的字母,求有多少棵树满足此序列。


思路:


首先根据dfs的过程可以得到如果一棵树有n个节点的话,他的序列长度为2n-1;所以如果给出的长度为m的话,节点数量n=(m+1)/2。所以如果说给出的序列长度是偶数的话,答案一定为0;即每个子树的dfs序列长度必定为奇数。


因为一段dfs序列可以对应一棵子树,考虑动态规划。


dp[l] [r] 表示所有dfs序列是s[l~r]的树的个数,划分依据为最后一棵子树的范围,即枚举最后一棵子树dfs序列的起点k,区间[k,r]表示这棵子树。根据上文我们可以知道该段区间的长度必定为奇数,所以k=l,l+2……r-2.因为必须要是子树,r-1只有两个节点,都是根节点,不是子树,所以枚举到r-2。


再来考虑状态计算。根据乘法原理,dp[l] [r]=l到k的序列构成的方案数×最后一棵子树的种类。对于后者,把根节点去掉后,又可以变成[k+1,r-1]的序列构成的方案数,这样就可以不断计算下去。


最后,并不是所有的状态都是合法的,因为是dfs,所以起点和终点一定是相同的,也就是说l,r,k的字符串的值都是相同的。


代码:

#include<bits/stdc++.h>
using namespace std;
char s[310];
typedef long long ll;
ll dp[310][310];
const int mod=1e9;
int main(){
    cin>>s+1;
    int n=strlen(s+1);
    if(n%2==0){
        puts("0");
        return 0;
    }
    for(int len=1;len<=n;len+=2){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            if(len==1) dp[l][r]=1;
            else{
                if(s[l]==s[r]){
                    for(int k=l;k<=r-2;k+=2){
                        if(s[l]==s[k]){
                            dp[l][r]=(dp[l][r]+dp[l][k]*dp[k+1][r-1])%mod;
                        }
                    }
                }
            }
        }
    }
    printf("%lld\n",dp[1][n]);
    return 0;
}

参考文献

目录
相关文章
|
27天前
|
算法 测试技术 定位技术
数据结构与算法——DFS(深度优先搜索)
数据结构与算法——DFS(深度优先搜索)
|
3月前
|
算法
DFS算法的实现
DFS算法的实现
54 3
|
5月前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
44 4
|
18天前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
70 0
|
27天前
|
算法 C++
【算法】DP背包问题(C/C++)
【算法】DP背包问题(C/C++)
|
27天前
|
人工智能 算法 BI
【算法】 线性DP(C/C++)
【算法】 线性DP(C/C++)
|
5月前
|
算法
基于仿射区间的分布式三相不对称配电网潮流算法matlab仿真
```markdown # 摘要 本课题聚焦于基于仿射区间的分布式三相配电网潮流算法在MATLAB2022a中的仿真。算法利用仿射运算处理三相不平衡情况及分布式电源注入,旨在提供比区间算法更精确的不确定区域。仿真结果展示了算法优势。核心程序设计考虑了PQ、PV及PI节点,将不同类型的节点转换统一处理,以适应含分布式电源的配电网潮流计算需求。 ``` 这个摘要以Markdown格式呈现,总字符数为233,满足了240字符以内的要求。
|
5月前
|
算法 Java
Java数据结构与算法:图算法之深度优先搜索(DFS)
Java数据结构与算法:图算法之深度优先搜索(DFS)
|
5月前
|
算法 索引
DFS算法及应用(二)
回溯:回溯就是DFS的一种,在搜索探索过程中寻找问题的解,当发现不满足求解条件时,就回溯返回,尝试其他路径。