tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 计算机软件及应用 >>

动态规划经典模型


9.常见DP类型

谢勇 湘潭大学信息工程学院 ericxieforever@gmail.com
2015-5-5 1

? ? ? ? ?

POJ 2955 大意 给你一个括号序列,求最长合法括号子序 列的长度 (序列长度不超过100)
Sample Input ((())) ()()() ([]]) )[)( ([][][) end Sample Output 6 6 4 0 6
2

2015-5-5

? ?

典型区间DP模型 如果找到一对匹配的括号[xxx]oooo,就 把区间分成两部分,一部分是xxx,一部分 是oooo,然后以此递归直到区间长度为1或 者为2

2015-5-5

3

dp[i][j]表示区间[i,j]之间的最长合法 括号子序列长度 ? dp[i][j] = min{dp[i+1][j], dp[i+1][k-1]+dp[k+1][j]+1 (i<=k<=j&&i和k是一对匹配的括号) }
?

2015-5-5

4

#define N 111 int dp[N][N]; char str[N];

int match(int x,int y){ return str[x]=='('&&str[y]==')' || str[x]=='['&&str[y]==']' || str[x]=='{'&&str[y]=='}'; }
int dfs(int s,int e){ int i,ret,t; if(e<s) return 0; if(e==s) return dp[s][e]=0; if(e-s==1) return dp[s][e]=match(s,e); if(dp[s][e]!=-1) return dp[s][e]; ret = dfs(s+1,e); for(i=s+1;i<=e;i++) if(match(s,i)){ t = dfs(s+1,i-1) + dfs(i+1,e) + 1; if(t>ret) ret = t; } return dp[s][e] = ret; } int main(){ int i,j,k,n; while(gets(str),str[0]!='e'){ n = strlen(str); memset(dp,-1,sizeof(dp)); dfs(0,n-1); printf("%d\n",dp[0][n-1]*2); } return 0; }

2015-5-5

5

? ?

POJ 2096 题意
? 一个软件有s个子系统,会产生n种bug 某人一

天发现一个bug,这个bug属于一个子系统,属 于一个分类 每个bug属于某个子系统的概率是 1/s,属于某种分类的概率是1/n 问发现n种bug, 每个子系统都发现bug的天数的期望。

2015-5-5

6

dp[i][j]表示目前已经找到i种bug,j个子系统的bug ,达到目标状态的期望天数 ? 显然,dp[n][s]=0;答案是dp[0][0]; ? dp[i][j]可以转化成以下四种状态:
?
? dp[i][j],发现一个bug属于已经有的i个分类和j个系统。

概率为(i/n)*(j/s); ? dp[i][j+1],发现一个bug属于已有的分类,不属于已有的 系统.概率为 (i/n)*(1-j/s); ? dp[i+1][j],发现一个bug属于已有的系统,不属于已有的 分类,概率为 (1-i/n)*(j/s); ? dp[i+1][j+1],发现一个bug不属于已有的系统,不属于已 有的分类,概率为 (1-i/n)*(1-j/s);
2015-5-5 7

2015-5-5

8

#define FD(i,n) for(i=(n)-1;i>=0;i--) #define N 1002 double dp[N][N];
int main() { int i,j,n,s; while(scanf("%d%d",&n,&s)!=EOF) { dp[n][s] = 0.0; FD(i,n+1) FD(j,s+1) { if(i==n&&j==s) continue; dp[i][j] = i*(s-j)*dp[i][j+1]+ (n-i)*j*dp[i+1][j]+ (n-i)*(s-j)*dp[i+1][j+1]+ n*s; dp[i][j] /= (n*s-i*j); } printf("%.4f\n",dp[0][0]); } return 0; }
2015-5-5 9

? ? ? ? ?

概率DP主要用于求解期望、概率等题目。 转移方程有时候比较灵活。 一般求概率是正推,求期望是逆推。 推荐几篇NOI论文:
? 《信息学竞赛中概率问题求解初探》
? 《浅析竞赛中一类数学期望问题的解决方法》 ? 《有关概率和期望问题的研究 》

2015-5-5

10

? ?

HDU 3555 题意
? 从1到N中包含49子序列的数的数目 ? From 1 to 500, the numbers that

include the sub-sequence "49" are "49","149","249","349","449","490","4 91","492","493","494","495","496","49 7","498","499", so the answer is 15.

2015-5-5

11

? ?

前面加一个数码 含49的
? 含49的,前面可以加0-9

?

不含49的

? 不含49的,但是首位是9的可以加4

? 不含49的,前面可以加0-9;去掉加了以后前两

位是49的。

2015-5-5

12

?

状态表示
? dp[i][0]表示i位长,含“49”的数的数目 ? dp[i][1]表示i位长,不含“49”的数的数目 ? dp[i][0] = dp[i-1][0]*10 + dp[i-2][1]

?

状态转移

? dp[i][1] = dp[i-1][1]*10 – dp[i-2][1]
? 边界条件 ? dp[0][1] = 1,dp[1][1] = 10
2015-5-5 13

位数

含49

不含49

1 2 3 4 5 6 7 8 9

0 1 20 299 3970 49401 590040 6850999 77919950

10 99 980 9701 96030 950599 9409960 93149001 922080050

2015-5-5

14

?

n = 0ak-1…a0

? 第i位可以取1到ai的数码

? 如果前面已经存在“49”,那么i长的不含49的也

? ans += ai * dp[i][0] ? ans += ai *dp[i][1] ? ans += dp[i-1][1]

需要加入,而第i位可以取1到ai的数码

? 如果前面没有存在49的数码,且ai > 4,加入

dp[i-1][1]

? 判断a[i+1,i]==49,设置出现标志,计算下一个数

码 ? 如果已经存在49,那么490…0也是解,ans++
2015-5-5

15

?
?

49
? 4*dp[1][0]+9*dp[0][0]+1 = 1

i

dp[i][0] dp[i][1]

548
? 5*dp[2][0]+dp[1][1]+ ? 4*dp[1][0]+ ? 8*dp[0][0] = 5*1+10 = 15

1 2 3 4

0 1 20 299

10 99 980 9701

?

4910
? ? ? ? ?

4*dp[3][0]+ 9*dp[2][0]+dp[1][1]+ 1*dp[1][0]+dp[1][1]+ 0*dp[0][0]+1 = 4*20+9*1+10+1*0+10+0*0+1 = 110
16

2015-5-5

#define N 20 LL dp[N][2]; void init(){ int i; dp[0][1] = 1; dp[1][1] = 10; for(i=2;i<N;i++){ dp[i][0] = dp[i-1][0]*10 + dp[i-2][1]; dp[i][1] = dp[i-1][1]*10 - dp[i-2][1]; }

}

int main(){ int i,len,tag,digit[N],cas; LL ans,n;
init();

scanf("%d",&cas); while(cas--){ scanf("%I64d",&n); for(len=0;n;n/=10) digit[len++] = n%10; digit[len] = 0; ans = 0; tag = 0; for(i=len-1;i>=0;i--){ ans += dp[i][0]*digit[i]; if(tag) ans += dp[i][1]*digit[i]; else if(digit[i]>4 && i) ans += dp[i-1][1]; if(digit[i+1]==4 && digit[i]==9) tag = 1; } printf("%I64d\n",ans+tag); } } return 0;

2015-5-5

17

? ?

一般题目形式为统计一个区间内符合某些 数码之间关系条件的数的个数 一般思路
? 先计算L长数码中的符合和不符合的个数(DP) ? 从高位到低位,按位统计(DP)

?

有些题可能需要使用大数(Java)

2015-5-5

18

? ?

?
?

POJ 1185 一个N*M方格组成的矩阵,每个方格可以放 大炮用P表示,不可以放大炮用H表示,大 炮可以攻击半径为2的十字,让放最多的大 炮,大炮之间不会互相攻击。 N<=100 M<=10

2015-5-5

19

? ?

?

如果我们从上到下安排炮位,那么炮是否 受到攻击,只和当前行的前两行相关。 因为M很小(M<=10),我们使用10位2进制表 示一行炮位的状态,1表示有炮,0表示无 炮 状态表示
? dp[i][Si][Si-1]表示第i行,其状态为Si,第i-

1行的状态为Si-1 时的最多炮位数(i>=2) s1中1的个数 ? dp[1][S1][S0] = cnt(S1)
2015-5-5

20

?

状态转移
? dp[i][Si][Si-1] = max{dp[i-1][Si-1][Si-2]

?

合法的状态
? mask & Si
? O(N23M)

+ cnt(Si)}

? mask = (Si-1|Si-2|Mi)

?

时间复杂度

为0表示合法

? 100*230 太大,TLE
2015-5-5 21

?

Si 必须合法,那么任意两个1之间距离需 要大于等于2,合法状态只有60个。
? f(n) = f(n-3) + f(n-1) ? f(1) = 2, f(2) = 3, f(3) = 4 ? f(10) = 60

? ?

先预处理出所有的合法状态及其1的个数 时间复杂度为
? O(N*|S|3) ? 2.16*107

2015-5-5

22

int dp[N][M][M],s[M],c[M],lmt[10],map[N],n,m; int ok(unsigned int x){ int t; if(x&x<<1) return 0; if(x&x<<2) return 0; return 1; } int cnt(unsigned int x){ int t; int a[8]={0,1,1,2,1,2,2,3}; for(t=0;x;x>>=3) t+=a[x&7]; return t; } void init(){ int i,j=1,k=0; for(i=0;i<(1<<10);i++) if(ok(i)){ s[k] = i; c[k] = cnt(i); if(i>((1<<j)-1)) lmt[j-1] = k,j++; k++; } lmt[9] = M; }
2015-5-5 23

void solve(){ int i,j,k,t,mask,tmp,ans=0; m = lmt[m-1]; memset(dp,0,sizeof(dp));

FU(j,m) if(!(map[1]&s[j])){ FU(k,m) dp[1][j][k] = c[j]; } for(i=2;i<=n;i++){ FU(j,m) FU(k,m) FU(t,m){ mask = s[k] | s[t] | map[i]; if(mask & s[j]) continue; tmp = dp[i-1][k][t] + c[j]; if(tmp > dp[i][j][k]) dp[i][j][k] = tmp; }
} FU(j,m) FU(k,m) if(dp[n][j][k]>ans) ans = dp[n][j][k]; printf("%d\n",ans);
24

}
2015-5-5

? ? ?

?

使用位表示状态,常见于在集合上的DP 一般常见某一维很小(使用位压缩存储表 示集合) 如果状态值大于2,可能需要使用3进制或 者4进制 注意转移时状态的合法性

2015-5-5

25

? ?

POJ 1655 题意
? 一棵树,找到一个点,其所有的子树中最大的子

树节点最少。 ? 节点1,其所有子树最大的子树节点数为2

2015-5-5

26

? ?

一种数据结构 定义
? 由n(n>=0)个节点的组成的集合 ? 没有节点,被称为空树 ? 非空树,一个特定节点被称为根节点(root)

? 剩下的n-1个点,被分成若干个不相交的集合
? 这些集合也是树,被称为子树

2015-5-5

27

?

一些术语
? 根节点 ? 子树 ? 叶子节点 ? 孩子节点
E

A B
F

C
G H

D
I J

? 父节点
? 兄弟节点 ? 树高
2015-5-5

K

L

M

28

?

树的一些性质
? n个节点,n-1条边 ? 无环,连通 ? 任意两点之间有且仅有一条路

2015-5-5

29

? ? ?

孩子兄弟 父节点
? 并查集里使用过

用邻接表
? 这是表示图的数据结构

? 树是稀疏图

2015-5-5

30

2015-5-5

31

? ?

多个链表组成 实现方式
? vector<int> G[N]; ? 这种方式可能会因为vector的容量扩展导致TLE ? 前向星 ? 邻接表是不是很像Hash时候的链地址法? ? 实现多个链表的一种常见实现方式。

2015-5-5

32

? ? ? ? ? ?

如果以P为根节点,那么存在 其孩子数+1棵子树 dp[i]表示以节点i作为根节 点的最大子树节点数 cnt[i]表示在原树里以节点 i作为根节点的子树的节点数 dp[p] = max{cnt[Ci], ncnt[p]} cnt[p]= sum{cnt[Ci]} + 1 cnt[leaf] = 1
33

2015-5-5

?

举例

2015-5-5

34

#define N 20000 #define max(x,y) ((x)>(y)?(x):(y)) int vectex[N]; int visit[N]; int vn,en; struct _edge{ int to; int next; }edge[N<<1]; void initGraph(){ memset(vectex,-1,sizeof(vectex)); memset(visit,0,sizeof(visit)); en = 0; } void addEdge(int from,int to){ edge[en].to = to; edge[en].next = vectex[from]; vectex[from] = en; en++; }
2015-5-5 35

int dp[N],c[N],rv,rp; void dfs(int u){ int i,v; visit[u] = 1; dp[u] = 0; c[u] = 1; for(i=vectex[u];i!=-1;i=edge[i].next){ v = edge[i].to; if(visit[v]) continue; dfs(v); c[u] += c[v]; if(dp[u]< c[v]) dp[u] = c[v]; } if(dp[u] < vn-c[u]) dp[u] = vn-c[u]; if(rv > dp[u]){ rv = dp[u]; rp = u + 1; } }

2015-5-5

36

void readGraph(){ int from,to,i; initGraph(); scanf("%d",&vn); FU(i,vn-1){ scanf("%d %d",&from,&to); addEdge(from-1,to-1); addEdge(to-1,from-1); } }
int main(){ int ca; scanf("%d",&ca); while(ca--){ readGraph(); rv = N; rp = -1; dfs(0); printf("%d %d\n",rp,rv); } return 0; }

2015-5-5

37

? ? ? ? ?

HDU WEB-DIY

?

★2014 湘潭大学 ACM程序设计作业9★ 开始时间 结束时间 密码:xtuacm2014

38

39


推荐相关:

动态规划的几种典型模型_图文.ppt

动态规划的几种典型模型 - 参考《算法艺术与信息学竞赛》... 动态规划的几种典型模型_计算机软件及应用_IT/计算机_专业资料。参考《算法艺术与信息学竞赛》 ...

动态规划经典模型.ppt

动态规划经典模型_计算机软件及应用_IT/计算机_专业资料。9.常见DP类型 谢

动态规划模型.pdf

动态规划模型_数学_自然科学_专业资料。2013/2/21 数学建模专题讲座 数学建模讲义最优化模型主讲人:穆学文西安电子科技大学数学系 Email:mxw1334@126.com ---动态...

动态规划经典案例详解(背包问题).pdf

动态规划经典案例详解(背包问题) - 动态规划经典案例详解之背包问题 【摘要】 本文主要从动态规划经典案例背包问题的动态规划设计思路出发, 结合具体实 例,对...

动态规划模型.doc

动态规划模型 - 第2讲 动态规划模型 动态规划是运筹学的一个分支,它是解 决多

动态规划_图文.ppt

动态规划 - 动态规划,动态规划算法 经典实例,动态规划算法,动态规划经典例题ppt,动态规划经典题目,动态规划状态转移方程,动态规划 背包问题,动态规划模型,01背包问题...

数模动态规划模型_图文.pdf

最优化原理与动态规划的基本方法 2 动态规划模型的建立与求解步骤建立动态规划模型的基本要求 动态规划的求解步骤 3 动态规划的应用举例 单位:数学与统计学院...

动态规划的很经典的教程.doc

动态规划的很经典的教程 - 动态规划的很经典的教程 引言:本人在做过一些题目后对 DP 有些感想,就写了这个总结: 第一节 动态规划基本概念 一,动态规划三要素:...

数学模型动态规划.doc

数学模型动态规划 - 动态规划 动态规划(dynamic programming)是运筹学的一个重要分支,它是解决多 阶段决策问题的一种有效的数量化方法.动态规划是由美国学者贝尔曼 ...

动态规划经典问题大合集.pdf

动态规划经典问题大合集_电脑基础知识_IT/计算机_专业资料。动态规划经典教程引言...2.6 其他问题还有一些题目虽和一写基本模型相似但又有区别,我也就不总结共性...

第9章 第4节 动态规划经典题_图文.ppt

第九章 动态规划第一节 动态规划的基本模型 第二节 动态规划与递推第三节 背包问题 第四节 动态规划经典题 动态规划程序设计是对解最优化问题的一种途径、一种...

动态规划的模型构建.ppt

动态规划模型构建_数学_自然科学_专业资料。动态规划模型构建长沙市雅礼中学 朱全民 NOIP的动态规划试题 ? ? ? ? ? ? ? ? ? 加分二叉树(2003)树型...

第二节_最优化原理与动态规划_图文.ppt

第二节_最优化原理与动态规划 - 第二节 最优化原理与动态规划的数学模型 ◆理解动态规划的基本概念和基本原理 一、动态规划方法导引 1. 全枚举法或穷举法。共...

动态规划的模型构建与优化方法_图文.ppt

动态规划模型构建与优化方法 - 动态规划模型 构建与优化 长沙市第一中学 曹利国 综述 ? ? ? 动态规划是运筹学的一个分支,是求解 决策过程最优化的数学方法。...

动态规划模型.pdf

动态规划模型 - 第十八章 动态优化模型 动态过程的另一类问题是所谓的动态优化问

用动态规划模型求解最短路问题的研究_论文.pdf

动态规划模型求解最短路问题的研究 - 动态规划法是求解具有多阶段的最短路径的算法,本文以动态规划理论为指导,研究了铺设管道最短路问题实例,采用顺序递推法和...

5.3建立动态规划数学模型的步骤(1)_图文.ppt

5.3建立动态规划数学模型的步骤(1) - 运筹学所有课件,全集!!精华!!... 运筹学 第五章 动态规划 §3 建立动态规划数学模型的步骤“最优化原理”是动态规划的核...

浅析1D1D动态规划的优化_图文.ppt

浅析1D1D动态规划的优化 浅析1D1D动态规划的优化 所谓1D/1D动态规划,指的是...f(x)=min{a(k)} (x-m+1<=k<=x) 显然这个方程是满足经典模型一的,...

4.3动态规划的建模与求解(经典运筹学)_图文.ppt

4.3动态规划的建模与求解(经典运筹学) - 4.3.1 建摸 1、理论依据 -

※动态规划经典教程.doc

动态规划经典教程 - dp经典 包涵所有dp 简单易懂 含大量例题... 动态规划经典教程 Directory 1.1 下降/非降子...2.6 其他问题 还有一些题目虽和一写基本模型...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com