动态规划题目.docx

动态规划题目.docxClB12AC2724B2机器分配总公司拥有高效生产设备M台,准备分给下属的N个公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其屮Mv=15,N<=10o分配原则:每个公司有权获得任意数目的设备,但总台数不得超过总设备数M。数据文件格式为:第一行保存两个数,第一个数是设备台数M,第二个数是分公司数N。接下来是一个M*N的矩阵,表明了第I个公司分配J台机器的盈利。用机器数来做状态,数组F[I,J]表示前I个公司分配J台机器的最大盈利。则状态转移方程为:F[LJl=Max{F[I-hK]+ValuefL初始值:F(0,0)=0时间复杂度O(N*M2)J-Kl(1<=I<=N,1<=J<=M,O<=K<=J)/JrX「3给你一个数字三角形,形式如下:123456789 10找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.、;(2\——/‘\1「8」八4」\、'/{3)(/、丿,3)7」八1JS「2J1)'/\2)':/\;(1,_、/⑶〔」一//、?^\\n-厂8」(^5厂1///[)-2J1)/!\/丿(4X)/5(3(4,一22)O“\J/-2、5,O(3,4)(,6©\(5、、04一/丿6(5%交错兀配(最长公共子串的改编)给你两排数字,只能将两排中数字相同的两个位置相连,而每次相连必须有两个匹配形成一次交错, 5 1 3 5 10XX12 1 5 5 3状态的表示一f[i,j]表示前i个第一排的数字和前j个第二排的数字搭配的最优值。(第一组交错),,(Ural1031)Ekaterinburg城到Sverdlovsk城有直线形的铁路线。两城Z间还有其他一些停靠站,总站数为N。各站按照离Ekaterinburg城的距离编号。Ekaterinburg城编号为1,Sverdlovsk城编号为N。1 2 34 5 6 7iskatavibug L| <X<=Ll时,<=L2时,<X<=L3吋,,所以有时候要买几次票做几次车才行。比如,在上面的例图中,2・6没有直达票,有几种买票方法可以从2・6,其中一种是买C2元的2・3车票,再买C3元的3-6车票。给定起点站和终点站还有L1,L2,L3,C1,C2,C3,^2的预处理,(费用是一样的啊 )因此在每种收费情况下,(N)的程序:forj:=lto3dobegink:=en-l;fori:=endowntobedobeginwhile(way[i]-way[k]<=l[j])and(k>=be)dodec(k);p[i][j]:=k+l;end;:=be+ltoendo {枚举当前状态}begincost[i]:=maxlongint;forj:=lto3do {枚举以前状态}beginif(p[i][j]<>i)and(cost[i]>cost[p[i][j]]+c|j])thencost[i]:=cost[p[i][j]]+c[j];end;end;文字游戏(fairfox邀请赛1)给你一份单词表,和一个句子。求出该句子能有多少中不同的划分方法•例如:单词是abcdabcd句子是abed他共有4种完全划分方案:ab/cda/b/c/da/b/cdab/c/d;当前状态就是单词在句子中向后靠的位置,以前状态就是确定这个单词位置以后,:F[i]:=F[i]+F[i-length(word|j])]101中有一题《前缀》..[i,j],表示的是在前i个字符中插入j个加号能达到的最小值,最后的答案也就是F[length(s),m].于是就有一个动规的方程: F[i,j]:二min(f[i,j],f[k,j-l]+num[k+l,i]) num[k+l,i]表示k++1个位