DP of DP

dp of dp是这样一类动态规划问题:在方程的转移中需要运用到dp来进行的dp问题。我们可以理解为动态规划的嵌套!其主要思想:
1.我们记问题为 #1
2.发现#1的子问题#2与#1具有相似性,是#1的某一种特例!
我们可以递归的定义出#3 ....#n.... 然后我们发现每一个问题都是可以依赖于其子问题进行动态规划的!
- POI97 06 某ZJ直接改为其省选题
- 留坑
- 留坑

我们先上一道老得不能再老得题目来感受一下:【POI97 06】【某ZJ直接改为其省选题】
Genotype 是一个有限的基因序列。它是由大写的英文字母A-Z组成,不同的字母表示不同种类的基因。一个基因可以分化成为一对新的基因。这种分化被一个定义的规则集合所控制。每个分化的规则可以用三个大写字母A1A2A3表示,含义为基因A1可以分化成A2A3

我们用S代表特种基因,繁殖genotype是从特种基因序列开始。根据给定的规则,它由被选择控制规则对基因不断进行繁殖而成。
任务
从文本文件GEN.IN 读入一个定义的规则集和一个想生成的genotypes 单词序列
对每一个给定的 genotype,根据给定的分化规则,检查是否它能从某一个确定特种基因序列生成,如果能,找到最小的序列长度,
将结果写入文本文件GEN.OUT.
输入
在文件GEN.IN 的第一行有一个整数n, 1 <= n <= 10000. 下面n 每一行为一个分化规则. 这些规则都由包含A – Z的三个大写字母组成.
接下来的10 行,每行有一个 genotype. Genotype由没有空格的单词组成,最多100 个英文大写字母.
输出
在文件GEN.OUT中有10行,在第I行应写入: 一个正整数――需要生成第I个genotypes的最小长度;或者单词 NIE, 如果不能生成对应的genotype。
一组输入输出样例:
GEN.IN:
6
SAB
SBC
SAA
ACA
BCC
CBC
ACBC

GEN.OUT:
1

乍一看题目,我们立刻有了一个DP的思想!

我们考虑 F[L]--表示1~L号字母最少需要多少个S才能拼好!

F[i]=F[j]+1(若 [j+1,i]区间可以由一个S得到)
额,这就很明显 判断条件居然又是一个DP问题
根据给的一些信息我们继续DP
考虑到一些原因我们定义

G[ch][i][j]--表示某一字母ch是否能变换成 [i,j]

对于ch的某一个模式变换ch->(ch1,ch2)
我们考察是否有
G[ch1][i][k] G[ch2][k+1][j]
时间复杂度不言而喻。。。。
这就是一道经典的DP套DP的题目。
代码:
http://ideone.com/wTom40
UPD 2015.08.14
上面那个写法稍微有点问题。
在Claris的帮助下我找到了真谛!
。。。位运算搞搞即可?
新代码哦

讲个历史咯:截图


Recent Posts

comments powered by Disqus