信息學聯(lián)賽知識：貪心策略的特點與在信息學競賽中的應用

　　貪心策略的特點與在信息學競賽中的應用

　　1、求最長路徑問題（NOI93）：

　　對一個不存在回路的有向圖，編程求出途經(jīng)結點數(shù)最多的一條路徑。有向圖存放在一個文本文件中，第0行為一個數(shù)字，為該圖的結點總數(shù)N，其下還有N行，每行有N個非0即1的數(shù)字。若第i行第j列的數(shù)字為1，則表示結點i到結點j存在由i指向j的邊，否則該數(shù)為0。

　　2、刪數(shù)問題的源程序：

　　輸入數(shù)據(jù)：一個高精度正整數(shù)N，所刪除的數(shù)字個數(shù)S。

　　輸出數(shù)據(jù)：去掉的數(shù)字的位置和組成的新的正整數(shù)。

　　Program Delete_digit;

　　Var n:string;{n是由鍵盤輸入的高精度正整數(shù)}

　　s,a,b,c:byte;{s是所要刪除的數(shù)字的個數(shù)}

　　data:array[1..200] of 0..9; {記錄刪除的數(shù)字所在位置}

　　begin

　　readln(n);

　　readln(s);

　　for a:=1 to s do

　　for b:=1 to length(n) do if n[b]>n[b+1] then {貪心選擇}

　　begin

　　delete(n,b,1);

　　data[a]:=b+a-1; {記錄所刪除的數(shù)字的位置}

　　break;

　　end;

　　while n[1]='0' do delete(n,1,1); {將字符串首的若干個"0"去掉}

　　writeln(n);

　　for a:=1 to s do writeln(data[a],' ');

　　end.

　　3、最優(yōu)乘車問題

　　輸入數(shù)據(jù)：輸入文件INPUT.TXT。文件的第行是一個數(shù)字M（1≤M≤100）表示開通了M條單向巴士線路，第2行是一個數(shù)字N（1<N≤500），表示共有N個車站。從第3行到第M+2行依次給出了第一條到第M條巴士線路的信息。其中第i+2行給出的是第i條巴士線路的信息，從左至右依次按行行駛順序給出了該線路上的所有站點，相鄰兩個站號之間用一個空格隔開。

　　輸出數(shù)據(jù)：輸出文件是OUTPUT.TXT。文件只有一行，為最少換車次數(shù)（在0，1，…，M-1中取值），0表示不需換車即可達到。如果無法乘車達到S公園，則輸出"NO"。

　　Program Travel;

　　var m:1..100; {m為開通的單向巴士線路數(shù)}

　　n:1..500; {n為車站總數(shù)}

　　result:array[1..501] of -1..100; {到某車站的最少換車數(shù)}

　　num:array[1..500,1..50] of 1..500; {從某車站可達的所有車站序列}

　　sum:array[1..500] of 0..50; {從某車站可達的車站總數(shù)}

　　check:array[1..500] of Boolean; {某車站是否已擴展完}

　　Procedure Init;

　　var f1:text;

　　a,b,c,d:byte;

　　data:array[1..100] of 0..100;

　　begin

　　assign(f1,'input.txt');

　　reset(f1);

　　readln(f1,m);

　　readln(f1,n);

　　result[501]:=100;

　　for a:=1 to m do

　　begin

　　for b:=1 to 100 do data[b]:=0;

　　b:=0;

　　repeat

　　inc(b);

　　read(f1,data[b]);

　　until eoln(f1);

　　for c:=1 to b-1 do

　　for d:=c+1 to b do

　　begin

　　inc(sum[data[c]]);

　　num[data[c],sum[data[c]]]:=data[d];

　　end;

　　end;

　　end;

　　Procedure Done;

　　var min,a,b,c,total:integer;

　　begin

　　fillchar(result,sizeof(result),-1);

　　result[1]:=0;

　　for c:=1 to sum[1] do result[num[1,c]]:=0;

　　b:=data[1,1];

　　repeat

　　for c:=1 to sum[b] do

　　if (result[num[b,c]]=-1) then result[num[b,c]]:=result[b]+1;

　　min:=501;

　　for c:=1 to n do if (result[c]<>-1) and (result[c]<result[min])

　　then min:=c;

　　b:=min;

　　until result[n]<>-1;

　　writeln(result[n]);{到達S公園的最少換車次數(shù)}

　　end;

　　begin

　　Init;

　　end.

　　4、最佳游覽路線問題

　　輸入數(shù)據(jù)：輸入文件是INPUT.TXT。文件的第一行是兩個整數(shù)M和N，之間用一個空格符隔開，M表示有多少條旅游街（1≤M≤100），N表示有多少條林蔭道（1≤N≤20000）。接下里的M行依次給出了由北向南每條旅游街的分值信息。每行有N-1個整數(shù)，依次表示了自西向東旅游街每一小段的分值。同一行相鄰兩個數(shù)之間用一個空格隔開。

　　輸出文件：輸出文件是 OUTPUT.TXT。文件只有一行，是一個整數(shù)，表示你的程序找到的最佳瀏覽路線的總分值。

　　Program Tour;

　　var m,n:integer; {M為旅游街數(shù)，N為林蔭道數(shù)}

　　data:array[1..20000] of -100..100;{data是由相鄰兩條林蔭道所分}

　　procedure Init; {隔的旅游街的最大分值}

　　var a,b,c:integer;

　　f1:text;

　　begin

　　assign(f1,'input.txt');

　　reset(f1);

　　read(f1,m,n);

　　for a:=1 to n-1 do read(f1,data[a]); {讀取每一段旅游街的分值}

　　for a:=2 to m do

　　for b:=1 to n-1 do

　　begin

　　read(f1,c);

　　if c>data[b] then data[b]:=c; {讀取每一段旅游街的分值，并選擇}

　　end; {到目前位置所在列的最大分值記入數(shù)組data}

　　close(f1);

　　end;

　　procedure Done;

　　var a,sum,result,c:integer;

　　f2:text;

　　begin

　　result:=0;

　　sum:=0;

　　a:=0;

　　while (a<n) do

　　begin

　　inc(a); {從數(shù)組的第一個數(shù)據(jù)開始累加，將累加所}

　　sum:=sum+data[a]; {得到的最大分值記入result}

　　if sum>result then result:=sum;

　　if sum<0 then sum:=0; {若當前累加值為負數(shù)，則從當前狀態(tài)起從新}

　　end; {累加}

　　assign(f2,'output.txt');

　　rewrite(f2);

　　writeln(f2,result);

　　close(f2);

　　end;

　　begin

　　Init;

　　Done;

　　end.