Codeforces 509F Progress Monitoring:区间dp【根据遍历顺序求树的方案数】
题目链接:http://codeforces.com/problemset/problem/509/F
题意:
告诉你遍历一棵树的方法,以及遍历节点的顺序a[i],长度为n。
问你这棵树有多少种可能的形态。
遍历方法:
used[1 ... n] = {0, ..., 0};
procedure dfs(v):
print v;
used[v] = 1;
for i = 1, 2, ..., n:
if (a[v][i] == 1 and used[i] == 0):
dfs(i);
dfs(1);
题解:
表示状态:
dp[i][j] = numbers
表示a[i to j]这些节点,以a[i]为根所能构成的树的方案数。
找出答案:
ans = dp[1][n]
如何转移:
dp[i][j]一定以a[i]为根,且第一个访问的子节点一定是a[i+1]。
所以将dp[i][j]分为三部分:
(1)根节点a[i]
(2)最左边的一棵子树a[i+1 to k]
(3)右边剩下的一堆节点a[k+1 to j]
那么根据乘法原理:
dp[i][j] = ∑ dp[i+1][k]*右边一堆节点的方案数
然而遍历是根据节点编号从小到大访问儿子节点的。
这就要求,对于后面的一堆节点,如果其中某一个a[x]要和a[i+1]在同一层,那么一定要有a[i+1]<a[x]。
又因为对于右边的一堆节点来说,最先访问到的肯定是a[k+1]。
所以就是要保证:a[i+1]<a[k+1] or a[k+1]不存在
这样就不用管后面的节点了,爱咋分咋分……
接下来考虑如何求右边一堆节点的方案数。
a[k+1 to j]形成森林的方法数 = a[k to j]以a[k]为根的子树的方法数。
所以右边一堆节点的方案数 = dp[k][j]
最终就是:
if(a[i+1]<a[k+1] || k==j)
dp[i][j] += dfs(i+1,k)*dfs(k,j);
用记忆搜搞就行。
边界条件:
dp[i][i] = 1
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 505
#define MOD 1000000007 using namespace std; int n;
int a[MAX_N];
long long dp[MAX_N][MAX_N]; long long dfs(int i,int j)
{
if(i==j) return ;
if(dp[i][j]!=-) return dp[i][j];
dp[i][j]=;
for(long long k=i+;k<=j;k++)
{
if(a[i+]<a[k+] || k==j)
{
dp[i][j]+=dfs(i+,k)*dfs(k,j);
dp[i][j]%=MOD;
}
}
return dp[i][j];
} int main()
{
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
memset(dp,-,sizeof(dp));
cout<<dfs(,n)<<endl;
}
最新文章
- ms-sql关联表操作
- maven项目引用外部jar
- 《JavaScript权威指南》学习笔记 第七天 DOM操作
- gradle providedCompile 与compile区别
- iOS开发Facebook POP动效库使用教程
- clang: error: no such file or directory: xxx.pch
- MSM8909平台 LED背光的控制
- 优秀的Markdown编辑器MarkdownPad2免费版使用全功能
- POJ 1062 昂贵的聘礼 (最短路)
- setbuffer和freopen做一个简单的日志组件
- sed命令详解及应用实例
- 14.5.2 Changing the Number or Size of InnoDB Redo Log Files 改变InnoDB Redo Log Files的数量
- JS 事件派发器EventDispatcher
- PL/SQL 游标 (实验七)
- proxmox网络
- Mybatis之基于XML的调用存储过程与手动回滚事务
- 从0开始搭建vue+webpack脚手架(二)
- 2017高教杯数学建模B 题分析
- tornado学习笔记
- 隔行扫瞄/逐行扫瞄的介绍(Interlaced / Progressive)