动态规划题目.doc

动态规划专题测试考试时间：3小时题一、递增序列(INCNEASING SEQUENCES)源程序名 INCSQ.? (PAS,C,CPP)可执行文件名 INCSQ.EXE输入文件名 INCSQ.IN 输出文件名 INCSQ.OUT给定一个数字串，请你插入若干个逗号，使得该数字串成为一个严格递增的数列且最后一个数要尽可能小，在这个问题中，前导的零是允许出现在数的前面的。输入输入数据仅含一行，为一个长度不超过80的数字串。输出输出一个严格递增且最后一数最小的数列，相邻两个数之间用一个逗号隔开，如果有多个数列满足要求，则输出第一个数最大的那个数列，若这样的解还不止一个，则输出第二个数最大的那个数列，以此类推。样例INCSQ.IN100000101INCSQ.OUT100,000101题二、DOLLARS源程序名 DOLLARS.? (PAS,C,CPP)可执行文件名 DOLLARS.EXE输入文件名 DOLLARS.IN 输出文件名 DOLLARS.OUT在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。输入输入文件的第一行是一个自然数N，1N100，表示戴维学习汇率的天数。接下来的N行中每行是一个自然数A，1A1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。输出输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。注意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。样例DOLLARS.IN5400300500300250DOLLARS.OUT266.66样例解释 (无需输出)Day 1 . changing 100.0000 美元= 400.0000 马克Day 2 . changing 400.0000 马克= 133.3333 美元Day 3 . changing 133.3333 美元= 666.6666 马克Day 5 . changing 666.6666 马克= 266.6666 美元题三、最大的算式源程序名 BIGEXP.? (PAS,C,CPP)可执行文件名 BIGEXP.EXE输入文件名 BIGEXP.IN 输出文件名 BIGEXP.OUT题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：N=5, K=2，5个数字分别为1、2、3、4、5，可以加成：1*2*(3+4+5)=241*(2+3)*(4+5)=45(1*2+3)*(4+5)=45输入输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中(2=N=15, 0=K=N-1)。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。输出输出文件仅一行包含一个整数，表示要求的最大的结果样例BIGEXP.IN5 21 2 3 4 5 BIGEXP.OUT120说明(1+2+3)*4*5=120题四 Kitty猫基因突变源程序：kitty.exe可执行程序：kitty.exe输入文件：kitty.in输出文件：kitty.out某大学生选修了生物基因工程学。教授提出了ABC编码方案是不断地按照 A 若S串全是0T（S）= B 若S串全是1 CT（S1）T（S2）否则把S串分成两个等长的子串S1和S2对Kitty猫基因01串表达式S进行改写，直至最终被改写成只含有字符“A”、“B”，“C”的符号串。学习的过程中，该学生协助教授做了一些基因突变育种的工作。但是实验过程中，该学生越来越佩服教授先前提出的基因编码方案，因为恰好基因ABC编码的长度说明了Kitty猫的品种优良程度，其ABC编码长度越短，品种越优良。教授考察了各种不同的Kitty猫，发现Super Samuel 星球上原有的各种Kitty猫的基因中都至少有w个基因单元0。而且经研究发现：在不同的位置上发生突变的成本Ci是不同的，而基因S突变成S的成本C（S，S）就是发生突变的那些基因单元的突变成本的总和。同时，由于实验室经费不足，教授没有足够多的经费来培育出W个基因单元0同时发生突变所能得到的最优良品种。为此，他只能以粗略地以突变成本C（S，S）+突变后基因的ABC编码长度T（S）为评价批标A（S，S）来确定将培育出的新品种，A（S，S）越小，其评价效果越好。教授总是培育出评价效果最好的那些突变品种。例如，K=3，即S串长度为23；C1、C2、Cn依次是10、10、5、6、3、2、1、2；w=2，即恰好每次都是2个基因单元0同时发生突变。此时基因的01串表达式s=11000101中的第三、四、五和第七基因单元都是0。有一种突变方案是第三个和第四个基因单元发生突变，突变后基因的01串表达S=11110101。因此其突变成本C（S，S）=C3+C4=5+6=11；其ABC编码T（S）=CBCCABCAB，编码长度是9。所以突变后得到的新品种的评价指标值A（S，S）=11+9=20。另外一种突变方案是第五个和第七个基因单元发生突变，突变后基因的01串表达式S=1100111。因此其突变成本C（S，S）=C5+C7=3+1=4；其ABC编码T（S）=CCBAB，编码长度是5。所以突变后得到的新品种的评价指标值A（S，S）=4+5=9。显然后一种方案的评价效果要比前一种方案好。经过计计算，同时突变两个基因单元的各种方案中评价效果最好的方案就是同时突变第五个和第七个基因单元的方案。现在请你编写程序帮该生找出评价效果最好的突变方案。输入：文件中第一行有两个正整数k和w，1k7，1w30；第二行存放的是长度为2k基因01串表达式；第三行有2k个整数，依次为突变成本C1、C2、C2k，