雙進程dp需要練習(xí)

?

【問題描述】

?某特種部隊接到一個任務(wù)，需要潛入一個倉庫。該部隊士兵分為兩路，第一路士兵已經(jīng)在正面

牽制住了敵人，第二路士兵正在悄悄地從后方秘密潛入敵人的倉庫。

?當他們到達倉庫時候，發(fā)現(xiàn)這個倉庫的鎖是一把很詭異的電子鎖，上面是一排按鈕，每個按鈕

上都有一個數(shù)字……10秒鐘后，總部返回了該鎖的技術(shù)信息。要解開這把鎖，首先要從左邊的第

一個按鈕開始向右按動，中間可以跳過某些按鈕，按動到最右邊的按鈕后，反向向左按動。最終，

每個按鈕都要按且僅按一次。每兩個相鄰按鈕上數(shù)字之差的總和的最小值，便是解開這把鎖的密碼。

?作為一支裝備精良的特種部隊，必須要在最短的時間內(nèi)完成任務(wù)，解開這把鎖，潛入倉庫。

【輸入文件】

?輸入文件force.in 第一行是一個n（2 <= n <= 1000）表示共有n個按鈕。

?第二行是n個正整數(shù)，代表從左至右各按鈕上的數(shù)字，數(shù)值均不超過2000。

【輸出文件】

?輸出文件force.out只有一個數(shù)，為這把鎖的密碼。

【輸入樣列】

5

1 2 3 4 5

【輸出樣列】

4

?

?

program force;
var
? cost,f:array[0..1001,0..1001] of longint;
? a:array[0..1001] of longint;
? n,ans:longint;

procedure init;
var i:longint;
begin
? assign(input,'force.in');reset(input);
? assign(output,'force.out');rewrite(output);
? fillchar(a,sizeof(a),0);
? ans:=100000000;
? readln(n);
? for i:=1 to n do read(a[i]);
end;

function min(a1,a2:longint):longint;
begin
? if (a1>a2) then exit(a2) else exit(a1);
end;

procedure main;
var i,j:longint;
begin
? for i:=0 to n do begin????? ? // ※ 小技巧?1只能取一次所以可以增加一個點0 但是從0跳到其他地方的權(quán)值都是0！

??? cost[0,i]:=0;
??? cost[i,0]:=0;
? end;
? for i:=1 to n do
??? for j:=1 to n do begin
???? ?if i=j then continue;
????? cost[i,j]:=abs(a[i]-a[j]);
?? ?end;
? fillchar(f,sizeof(f),$7);
? f[0,0]:=0;
? for i:=0 to (n-1) do
??? for j:=i to n do begin
????? f[i,j+1]:=min(f[i,j+1],f[i,j]+cost[j+1,j]);
????? f[j,j+1]:=min(f[j,j+1],f[i,j]+cost[j+1,i]);?????????//從我設(shè)置的狀態(tài)來看 都是小的在前面大的在后面 所以從i跳到j(luò)+1就變成了[j,j+1]
??? end;
? for i:=1 to n do if (ans>f[i,n]) then ans:=f[i,n]+cost[i,n];
? writeln(ans);
end;

procedure terminate;
begin
? close(input);close(output);
end;

begin
? init;
? main;
? terminate;
end.

轉(zhuǎn)載于:https://www.cnblogs.com/ushiojamie/archive/2011/10/21/2220762.html

總結(jié)

以上是生活随笔為你收集整理的特种部队【动态规划】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。