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



推荐相关:

动态规划阶段总结之基础篇[必看]

我个人在感觉上觉得 01 背包这个模型其实和线性模型是非常相似的,但作为一个经典模型,我还是把 他独立出来了 解决的,只有当权值较小时,才可以使用动态规划解决...


运用动态规划模型解决最短路径问题 3

运用动态规划模型解决物流配送中的最短 路径问题摘要:随着现代社会的高速发展,物流...文献 ?6? 详细分析了经典方法的利弊之后,提出将邻接矩阵上三 角和下三角复制...


生产与库存的动态规划模型

建立模型Ⅱ 建立模型Ⅱ 以上用混合整数规划求解过多阶段生产计划,实际上,这是一类 典型动态优化问题,与用变分法建立连续动态优化模型不同的是, 多阶段生产计划...


零件加工时间最优化的动态规划模型

零件加工时间最优化的动态规划模型 - 零件加工时间最优的动态规划模型 摘要 零件加工最有时间问题是典型动态规划问题。建立一个动态规划模型,按 照这类问题的基本...


实现设定目标成本的动态规划模型

龙源期刊网 http://www.qikan.com.cn 实现设定目标成本的动态规划模型 作者:韩庆兰 黄凤 来源:《新会计》2013 年第 03 期 【摘要】在面向供应链节点企业内部自...


实验四2求解动态规划模型

实验四2求解动态规划模型_数学_自然科学_专业资料。(一) 实验目的:用 WinQSB 软件求解动态规划中的背包问题及生产与存储问题。 (二) 内容与要求:求解下列两例。...


动态规划阶段总结之基础篇[必看]

动态规划阶段总结之基础篇 by Zc [序言] 动态规划是信息学竞赛中最重要的知识...[j+1..i] 为一个基元 更复杂一点的就是二维的串模型,例如经典的 LCS ...


生产与存储的动态规划模型

建立模型Ⅱ 3.2 建立模型Ⅱ 以上用混合整数规划求解过多阶段生产计划,实际上,这是一类典型动态优化问题, 与用变分法建立连续动态优化模型不同的是, 多阶段...


数学建模动态规划库存问题

数学建模动态规划库存问题_数学_自然科学_专业资料。数学建模,动态规划,随机库存随机...六、 模型优缺点分析 6.1 模型优点 (1) 该模型以所有客户库存费用最小为...


基于动态规划的面试时间优化模型

2015 年 4 月 27 日 基于动态规划的面试时间优化模型 摘要 现代信息社会中,求职...比较典型的情况是用人单位或组织单位设置了几个阶段的面试,参加面试的人员 必须...

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