動(dòng)態(tài)規(guī)劃練習(xí)試題和解答-文庫吧
2025-07-07 00:24 本頁面
【正文】 文件的第一行是兩個(gè)整數(shù)m和k (1〈=k〈=m〈=500)。第二行有m個(gè)整數(shù)P1，P2，…，Pm，這m個(gè)整數(shù)均為正整數(shù)且都不超過1000000。每?jī)蓚€(gè)整數(shù)之間用空格分開。輸出格式：文件有k行，每行有兩個(gè)正整數(shù)。整數(shù)之間用空格分開。第I行的兩個(gè)整數(shù)ai和bi，表示第I號(hào)抄寫員所分配得到的書稿的起始編號(hào)與終止編號(hào)。動(dòng)態(tài)規(guī)劃題參考程序：題1：解決問題：例子的上下部分之差是6+1+1+1（1+5+3+2）=（61）+（15）+（13）+（12）=2，而翻轉(zhuǎn)最后一個(gè)骨牌后，上下之差變?yōu)椋?1）+（15）+（13）+（21）=0。由此看出，一個(gè)骨牌對(duì)翻轉(zhuǎn)策略造成影響的是上下兩數(shù)之差，骨牌上的數(shù)則是次要的了。這么一來，便把骨牌的放置狀態(tài)由8個(gè)數(shù)字變?yōu)?個(gè)： 5 4 2 1，翻轉(zhuǎn)時(shí)只需取該位數(shù)字的相反數(shù)就行了。在本題中，因?yàn)楦鞴桥频姆D(zhuǎn)順序沒有限定，所以不能按骨牌編號(hào)作為階段來劃分。怎么辦呢？考慮到隱含階段類型的問題可以按狀態(tài)最優(yōu)值的大小來劃分階段。于是，我們以骨牌序列上下兩部分的差值I作為狀態(tài)，把達(dá)到這一狀態(tài)的翻轉(zhuǎn)步數(shù)作為狀態(tài)值，記為f（I）。便有f（I）=min{f（I+j）+1} （12〈=j=12,j為偶數(shù)，且要求當(dāng)前狀態(tài)有差值為j/2的骨牌）。這里，I不是無限增大或減小，其范圍取決于初始骨牌序列的數(shù)字差的和的大小。具體動(dòng)態(tài)規(guī)劃時(shí)，如例題，我們以f（2）=0起步，根據(jù)骨牌狀態(tài)，進(jìn)行一次翻轉(zhuǎn)，可得到f（12）=1，f（6）=1，f（2）=1，f（0）=1，由于出現(xiàn)了f（0），因此程序便可以結(jié)束，否則將根據(jù)四個(gè)新狀態(tài)繼續(xù)擴(kuò)展，直至出現(xiàn)f（0）或者無法生成新狀態(tài)為止。注意：在各狀態(tài)，除記錄最少步數(shù)外，還需記錄到達(dá)這一狀態(tài)時(shí)各骨牌的放置情況；而當(dāng)?shù)竭_(dá)某一狀態(tài)發(fā)現(xiàn)已記錄有一種翻轉(zhuǎn)策略時(shí)，則取步數(shù)較小的一種。程序如下：program domino。type tp=array[1..6] of integer。var t:array[1..6000] of ^tp。 {記錄骨牌擺放狀態(tài)}f:array[6000..6000] of integer。{記錄達(dá)到某個(gè)差值的最少步數(shù)}l:array[1..6000] of integer。{擴(kuò)展隊(duì)列}tt:tp。 i,j,n,m,x,y,ft,re:integer。 f1,f2:text。procedure init。{程序初始化}begin assign(f1,39。39。)。 reset(f1)。 assign(f2,39。39。)。 rewrite(f2)。 m:=0。 ft:=0。re:=1。new(t[1])。 fillchar(t[1]^,sizeof(t[1]^),0)。 fillchar(f,sizeof(f),0)。 fillchar(tt,sizeof(tt),0)。 readln(f1,n)。 for i:=1 to n do begin readln(f1,x,y)。 if xy then begin x:=xy。 inc(m,x)。 inc(tt[abs(x)])。 if x0 then inc(t[1]^[x])。 end。 end。 if m=0 then begin writeln(f2,0)。 close(f2)。 halt。 end。 {處理步數(shù)為零的情況} l[1]:=m。 f[m]:=1。end。procedure main。{主過程}
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1