动态规划题目

《动态规划题目》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、ClB12AC2724B2机器分配总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其屮Mv=15,N<=10o分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。数据文件格式为：第一行保存两个数，第一个数是设备台数M,第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。用机器数来做状态，数组F[I,J]表示前I个公司分配J台机器的最大盈利。则状态转移方程为：F[LJl=Ma

2、x{F[I-hK]+ValuefL初始值:F(0,0)=0时间复杂度O(N*M2)J-Kl(1<=I<=N,1<=J<=M,O<=K<=J)/JrX「3给你一个数字三角形，形式如下:12345678910找出从第一层到最后一层的一条路，使得所经过的权值之和最小或者最大.、;(2——/‘1「8」八4」、'/{3)(/、丿，3)7」八1JS「2J1)'/2)':/;(1,_、/⑶〔」一//、？^-厂8」(^5厂1///[)-2J1)/!/丿(4X)/5(3(4,一22)O“J/-2、5,O(3,4)(,6©(5、、04一

3、/丿6(5%交错兀配（最长公共子串的改编）给你两排数字，只能将两排中数字相同的两个位置相连，而每次相连必须有两个匹配形成一次交错，交错的连线不能再和别的交错连线有交点.问这两排数字最多能形成多少个交错匹配.221513510XX121553状态的表示一f[i,j]表示前i个第一排的数字和前j个第二排的数字搭配的最优值。当前的状态就是当前你枚举到的一组交错的后面两个位置.例如上图中当前状态是3和1（第一组交错），枚举他的以前状态就有13.这样在13之前会有一个最优值存在，因此可以由此得到31的最优值.买车票(Ural1031)Ekateri

4、nburg城到Sverdlovsk城有直线形的铁路线。两城Z间还有其他一些停靠站，总站数为N。各站按照离Ekaterinburg城的距离编号。Ekaterinburg城编号为1,Sverdlovsk城编号为N。1234567iskatavibugL

5、Sverdlovsk某两站之间车票价格由这两站的距离x决定.当0

6、6,其中一种是买C2元的2・3车票，再买C3元的3-6车票。给定起点站和终点站还有L1,L2,L3,C1,C2,C3,求出要从起点到终点最少要花多少钱.预处理很容易想出一个N^2的预处理,但是那样是会超时的.由于尽量要让车站离得远(费用是一样的啊)因此在每种收费情况下，每个车站的以前状态车站一定是递增的序列.这里是只要O(N)的程序：forj:=lto3dobegink:=en-l;fori:=endowntobedobeginwhile(way[i]-way[k]<=l[j])and(k>=be)dodec(k);p[i][j]：=k+

7、l；end;数组PliJUl表示的是I状态的笫j种以前状态.动态规划的部分fori:=be+ltoendo｛枚举当前状态｝begincost[i]:=maxlongint;forj:=lto3do｛枚举以前状态｝beginif(p[i][j]<>i)and(cost[i]>cost[p[i][j]]+c

8、j])thencost[i]:=cost[p[i][j]]+c[j];end;end;文字游戏(fairfox邀请赛1)给你一份单词表，和一个句子。求出该句子能有多少中不同的划分方法•例如:单词是abcdabcd句子是abed他共有4种完

9、全划分方案：ab/cda/b/c/da/b/cdab/c/d;当前状态就是单词在句子中向后靠的位置，以前状态就是确定这个单词位置以后,除掉这个单词长度后的一个位置.状态转移方程是:F[i]:=F[i]+F[i-length(word

10、j])]101中有一题《前缀》也是类似的题目.最佳加法表达式有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中.使得所形成的算术表达式的值最小.用f[i,j],表示的是在前i个字符中插入j个加号能达到的最小值，最后的答案也就是F[length(s),m].于是就有一个动规的方程：F[i,j]:二

11、min(f[i,j],f[k,j-l]+num[k+l,i])num[k+l,i]表示k+1位到i位所形成的数字.这里显然是把加号插入了第k+1个位置上.巴比伦塔问题描述：有很多的不同种类的立