問題描述:美麗的萊茵河畔,每邊都分布著N個城市,兩邊的城市都是唯一對應的友好城市,現需要在友好城市開通航線以加強往來.但因為萊茵河常年大霧,如果開設的航線發生交叉現象就有可能出現碰船的現象.現在要求近可能多地開通航線并且使航線不能相交!
假如你是一個才華橫溢的設計師,該如何設置友好城市間的航線使的航線數又最大又不相交呢?
分析:此問題可以演化成求最大不下降序列來完成.源程序如下:
program?dongtai;?
{動態規劃之友好城市航線設置問題}
var
?d:array[1..1000,1..4]?of?integer;
?i,j,k,n,L,p:integer;
?procedure?print(L:integer);?{打印結果}
?begin
?writeLn('最多可設置的航線數是?:?',k);
?repeat
?writeLn(d[L,1]:4,d[L,2]:4);?{輸出可以設置航線的友好城市代碼}
?L:=d[L,4]
?untiL?L=0
?end;
begin
?writeLn('輸入友好城市對數:?');
?readLn(n);
?writeLn('輸入友好城市對（友好城市放在同一行:');?{輸入}
?for?i:=1?to?n?do
?readLn(d[i,1],d[i,2]);?{D[I，1]表示起點，D[I，2]表示終點}
?for?i:=1?to?n?do
?begin
?d[i,3]:=1;?{D[I，3]表示可以設置的航線條數}
?d[i,4]:=0?{D[I，4]表示后繼，即下一條航線從哪里開始設置，為0表示不能設置下一條航線}
?end;
for?i:=n-1?downto?1?do?{從倒數第二個城市開始規劃}
?begin
?L:=0;?p:=0;?{L表示本城市后面可以設置的航線數，P表示下條航線從哪個城市開始}
?for?j:=i+1?to?n?do?{找出本城市后面可以設置的最大航線數和小條航線到底從哪個城市開始設置}
?if?(d[i,2]?L)?then?
?{如果本城市I的終點小于后面城市的終點（即不相交）}?{并且此城市后面可以設置的航線數大于L}
?begin
?L:=d[j,3];?{那么L等于城市J的可以設置航線數}
?p:=j?{P等于可以設置下條航線的城市代碼}
?end;
?if?L>0?then?{如果本城市后面總共可以設置的航線數>0則}
?begin
?d[i,3]:=L+1;?{本城市可以設置的航線數在下個城市可以設置航線數的基礎上加1}
?d[i,4]:=p?{D[I，4]等于本城市后續城市的代碼}
?end
?end;
?k:=d[1,3];?{K為可以設置最大航線數，假設初值為第一個城市可以設置的航線數}
?L:=1;?{L為城市代碼，初值為第一個城市}
?for?i:=2?to?n?do?{找出可以設置航線的最大值，賦值給K，同時L記下哪個可以設置最大航線數的城市代碼}
?if?d[i,3]>k?then
?begin
?k:=d[i,3];
?L:=i
?end;
?for?i:=1?to?n?do?{打印結果，因為有可能有多種方案，所以只要哪個城市可以設置的航線數等于最大值K就打印結果}
?if?d[i,3]=k?then?print(i)
end.