動(dòng)態(tài)規(guī)劃解析word版-展示頁(yè)
2025-01-28 04:10本頁(yè)面
【正文】 :=i1。 last:=n。 fillchar(bak,sizeof(bak),true)。 end。 for i:=1 to n do for j:=2 to n do begin k:=((i+j2) mod n)+1。 var i,j,k,first,last:Word。 end。 end。 while ilast do begin stone1[i]:=s。 if last=first then s:=tot[last]tot[first1] else s:=tot[last]+tot[n]tot[first1]。 writeln。)。 write(stone1[i],39。39。 if first=last then exit。 out((rock_k[first,last] mod n)+1,last)。 var i,s:Word。 end。 fillchar(rock_k,sizeof(rock_k),0)。 var i:Word。 end。)。 assign(output,39。 for i:=1 to n do tot[i]:=tot[i1]+stone[i]。 close(input)。 readln(n)。)。 begin assign(input,39。procedure init。 end。 end。 if try(now,rock_best^[first,last],job) then begin rock_best^[first,last]:=now。 begin k:=first。 var k:Word。 end。job:byte):boolean。 end。 begin if first=last then s1:=tot[last]tot[first1] else s1:=tot[n]+tot[last]tot[first1]。function count(first,k,last:Word):longint。 bak:Tbak。 stone,tot:Tstone。 var rock_best:^Trock_best。 Tstone = Array[0..100] of word。 type Trock_best = Array[1..100,1..100] of longint。初始時(shí)f[k,k]=0(1=k=n)。根據(jù)合并規(guī)則，f[i,j]的解只于f[i,k],f[k+1,j](i=kj)的解有關(guān)，即問(wèn)題的最優(yōu)解包含了子問(wèn)題的最優(yōu)解，具備最優(yōu)子結(jié)構(gòu)。end.第二題 石子合并設(shè)f[i,j](i=j)表示將第i堆到第j堆石子合并為一堆所得的最大分?jǐn)?shù)（最小時(shí)類(lèi)似）。 main2。begin input。 end。 end。 if k=0 then begin o2:=o2+1。 for i:=1 to t do begin k:=0。 begin for i:=0 to t do l[i]:=maxint。 end。 end。 for j:=i+1 to t do if (l[j]k)and(d[i]=d[j]) then k:=l[j]。 begin l[t]:=1。 end。 writeln(o1)。Output:39。procedure output。 o2:=0。 t:=i。 read(d[i])。 i:=0。input:39。 fillchar(l,sizeof(l),0)。procedure input。var d,l : arr。附源程序：const max = 10000。(0=kn,a[n]=a[k] ) 設(shè)a[0]= maxint,f[0]=0。第一題 導(dǎo)彈攔截本題第一問(wèn)實(shí)際上是給出數(shù)列a1..an,求最長(zhǎng)非遞增序列的長(zhǎng)度，{容易想到以n來(lái)劃分子問(wèn)題，即分別求a1..an1, a1..an2, …, a1,中最長(zhǎng)非遞增序列長(zhǎng)度，但各級(jí)子問(wèn)題之間不易建立轉(zhuǎn)化關(guān)系}將子問(wèn)題具體一些，我們可以用f[k]表示數(shù)列a1..ak中以ak結(jié)尾的最長(zhǎng)非遞增序列的長(zhǎng)度，題目所求即為max{f[1..n]}。轉(zhuǎn)移方程為f[n]=max{f[k]}+1。第二問(wèn)可以用貪心做，設(shè)攔截前k個(gè)導(dǎo)彈用o2個(gè)系統(tǒng)，其最后攔截的高度分別為l[1]..l[o2],則攔截第k+1個(gè)導(dǎo)彈時(shí)，找能夠攔截這枚導(dǎo)彈的系統(tǒng)中最后攔截高度最小的，若沒(méi)有這樣的系統(tǒng)則新增一個(gè)系統(tǒng)。type arr = array[0..max]of integer。 i,j,k,m,n,o1,o2,t : longint。 begin fillchar(d,sizeof(d),0)。 writeln(39。)。 repeat i:=i+1。 until eoln。 o1:=0。 end。 begin writeln(39。)。 writeln(o2)。procedure main1。 for i:=t1 downto 1 do begin k:=0。 l[i]:=k+1。 for i:=1 to t do if l[i]o1 then o1:=l[i]。procedure main2。 o2:=1。 for j:=1 to o2 do if (l[j]=d[i])and(l[j]=l[k]) then k:=j。 k:=o2。 l[k]:=d[i]。 end。 main1。 output。問(wèn)題所求即為f[1,n]。轉(zhuǎn)移方程為f[i,j]={f[i,k]+f[k+1,j]}+d[p]。附源程序：Program gether_stone。 Trock_k = Array[1..100,1..100] of byte。 Tbak = Array[1..100] of boolean。 rock_k:Trock_k。 stone1:Tstone。 n:Word。 var s1:longint。 count:=rock_best^[first,k]+rock_best^[(k mod n)+1,last]+s1。function try(now,old:longint。 begin if ((job=1) and (nowold)) or ((job=2) and (nowold)) then try:=true else try:=false。procedure get(first,last,job:integer)。 now:longint。 while klast do begin now:=count(first,k,last)。 rock_k[first,last]:=k。 k:=(k mod n)+1。 end。 var i:Word。39。 reset(input)。 for i:=1 to n do read(stone[i])。 tot[0]:=0。 new(rock_best)。39。 rewrite(output)。procedure into(job:byte)。 begin if job=1 then fillchar(rock_best^,sizeof(rock_best^),$1) else fillchar(rock_best^,sizeof(rock_best^),0)。 for i:=1 to n do rock_best^[i,i]:=stone[i]。procedure out(first,last:byte)。 begin if not(((first mod n)+1=last) or (first=last)) then begin out(first,rock_k[first,last])。 end。 for i:=1 to n do if bak[i]=true then begin if (i=first) or (i=(rock_k[first,last]mod n)+1) then write(39。)。 39。 end。 bak[(rock_k[first,last] mod n)+1]:=false。 i:=first。 i:=(i mod n)+1。 stone1[last]:=s。procedure work(job:byte)。 begin into(job)。 get(i,j,job)。 stone1:=stone。 first:=1。 for i:=2 to n do if ((rock_best^[i,i1]rock_best^[first,last]) and (job=1)) or ((rock_best^[i,i1]rock_best^[first,last]) and (job=2)) then begin first:=i。 end。 writeln(tot[n])。begin init。 work(2)。end.第三題 乘積最大問(wèn)題給出了一個(gè)數(shù)字串s，求向其中加k個(gè)乘號(hào)后的最大乘積。問(wèn)題所求即為f[n,k]。設(shè)num[i,j]表示串s[i..j]所表示的數(shù)字，動(dòng)態(tài)規(guī)劃的轉(zhuǎn)移方程為f[i,j]={f[p,j1]*num
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1