参考.
\(Description\)
将\(1,2,\cdots,n(n\leq 300)\)依次入栈/出栈,并满足\(m(m\leq 90000)\)个形如\(x\)要在\(y\)之前出栈的限制,问合法的出栈序列有多少种。
\(Solution\)
没有限制就是个卡特兰数,但有了限制就要考虑好好DP了。。
序列的入栈&出栈顺序可以构成一棵二叉树,且每一棵子树中的点一定比该子树的根节点出栈早。
\(f[i][j]\)表示子树根节点为\(i\),其中的点是\(i\sim j\),\(i+1\sim j\)都比\(i\)出栈早。初始为:\(f[i][i]=1\).
无限制的DP方程就是: $$f[i][j]=\sum_{k=i+1}^jf[i][k-1]*f[k][j]$$
(这个是倒着枚举\(i\)的)
如果有限制,直接在DP完\(f[i][\ ]\)后把非法的\(f[i][\ ]\)设成0就行了。。
如果\(j\)要在\(k\)前出栈(\(j<k\)),那么\(f[j][k],f[j][k+1],\cdots\)都是非法的(\(f[\ ][\ ]\)当然是处理小的那个了)。
在\(j>k\)时,\(f[k][1],\cdots,f[k][j-1]\)是非法的。
最后的答案应是\(f[0][n]\).
注意如果限制有\(i\)在\(i\)前,那么直接0。
好像可以在\(f[\ ][\ ]\)上差分做,不看了。。https://ksmeow.moe/numbers_hdu5181_sol/
//483MS 1868K
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define mod (1000000007)
const int N=305;
int n,L[N],R[N],f[N][N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
int T=read(),m; bool flag;
while(T--)
{
flag=0;
n=read(),m=read();
for(int i=0; i<=n; ++i) L[i]=0,R[i]=n+1;
for(int x,y,i=1; i<=m; ++i)
{
x=read(),y=read();
if(x<y) R[x]=std::min(R[x],y);
else if(x>y) L[y]=std::max(L[y],x);
else flag=1;
}
if(flag) {puts("0"); continue;}
memset(f,0,sizeof f);
for(int i=n; ~i; --i)
{
f[i][i]=1;
for(int j=i+1; j<=n; ++j)
for(int k=i+1; k<=j; ++k)
(f[i][j]+=1ll*f[i][k-1]*f[k][j]%mod)%=mod;
for(int j=1; j<L[i]; ++j) f[i][j]=0;
for(int j=R[i]; j<=n; ++j) f[i][j]=0;
}
printf("%d\n",f[0][n]);
}
return 0;
}
HDU.5181.numbers(DP)的更多相关文章
-
hdu 5181 numbers——思路+区间DP
题目:http://acm.hdu.edu.cn/showproblem.php?pid=5181 题解:https://www.cnblogs.com/Miracevin/p/10960717.ht ...
-
hdu 5181 numbers
http://acm.hdu.edu.cn/showproblem.php?pid=5181 题意: 有一个栈,其中有n个数1~n按顺序依次进入栈顶,在某个时刻弹出. 其中m个限制,形如数字A必须在数 ...
-
HDOJ(HDU).1058 Humble Numbers (DP)
HDOJ(HDU).1058 Humble Numbers (DP) 点我挑战题目 题意分析 水 代码总览 /* Title:HDOJ.1058 Author:pengwill Date:2017-2 ...
-
hdu 3709 数字dp(小思)
http://acm.hdu.edu.cn/showproblem.php?pid=3709 Problem Description A balanced number is a non-negati ...
-
hdu 4352 数位dp + 状态压缩
XHXJ's LIS Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total ...
-
hdu 4123 树形DP+RMQ
http://acm.hdu.edu.cn/showproblem.php? pid=4123 Problem Description Bob wants to hold a race to enco ...
-
hdu 4507 数位dp(求和,求平方和)
http://acm.hdu.edu.cn/showproblem.php?pid=4507 Problem Description 单身! 依旧单身! 吉哥依旧单身! DS级码农吉哥依旧单身! 所以 ...
-
hdu 4283 区间dp
You Are the One Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)T ...
-
HDU 2829 区间DP &; 前缀和优化 &; 四边形不等式优化
HDU 2829 区间DP & 前缀和优化 & 四边形不等式优化 n个节点n-1条线性边,炸掉M条边也就是分为m+1个区间 问你各个区间的总策略值最少的炸法 就题目本身而言,中规中矩的 ...
随机推荐
-
为什么NOLOCK查询提示是个不明智的想法
一些人总当NOLOCK查询提示是SQL Server里的加速器,因为它避免了大量的死锁情景.在这篇文章里,我想向你展示下为什么NOLOCK查询提示是个不好的想法. 脏读(Dirty Reads) NO ...
-
linux jmail乱码
在Windows 里面,标题和内容都正常, 在linux里面,--- 1.字符串 more /etc/sysconfig/i18n export LANG=en_US.UTF-8 ====默认是e ...
-
POJ 2391 容牛问题
题目大意:给定一个无向图,点i处有Ai头牛,点i处的牛棚能容纳Bi头牛,求一个最短时间T使得在T时间内所有的牛都能进到某一牛棚里去.(1 <= N <= 200, 1 <= M &l ...
-
npm 模块安装机制简介
npm 是 Node 的模块管理器,功能极其强大.它是 Node 获得成功的重要原因之一. 正因为有了npm,我们只要一行命令,就能安装别人写好的模块 . $ npm install 本文介绍 npm ...
-
Cocos2d-X游戏开发之Windows7+VS2010环境搭建(亲测)
Cocos2d—X游戏引擎,提供Mac系统下的Xcode开发和Windows系统的VS开发,应该是比较常用的2种. 使用Mac以后,就会发现使用Xcode开发实在是福分啊.VS开发步骤繁琐,调试效率低 ...
-
深入理解计算机系统(2.5)------C语言中的有符号数和无符号数以及扩展和截断数字
上一篇博客我们讲解了计算机中整数的表示,包括无符号编码和补码编码,以及它们之间的互相转换,个人觉得那是非常重要的知识要点.这篇博客我们将介绍C语言中的有符号数和无符号数以及扩展和截断数字. 1.C语言 ...
-
NEO从入门到开窗(4) - NEO CLI
一.唠叨两句 首先,我们都知道区块链是去中心化的,其中节点都是对等节点,每个节点都几乎有完整的区块链特性,CLI就是NEO的一个命令行对等节点,当然也有GUI这个项目,图形化的NEO节点.节点之间需要 ...
-
php正则字符串提取汉字
/*$str 为输入.输出字符串变量*/ preg_match_all('/[\x{4e00}-\x{9fff}]+/u', $str, $matches); $str = join('', $mat ...
-
vue - 指令系统
指令系统: 所谓指令系统,大家可以联想咱们的cmd命令行工具,只要我输入一条正确的指令,系统就开始干活了. 在vue中,指令系统,设置一些命令之后,来操作我们的数据属性,并展示到我们的DOM上. 1. ...
-
c#-MVC基础操作-数据的展示及增删改、登录页面及状态保持
一.数据展示 1.View代码: <%@ Page Language="C#" Inherits="System.Web.Mvc.ViewPage<dynam ...