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