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