来自：查字典高考网 2009-11-12
贪心策略的特点与在信息学竞赛中的应用
1、求最长路径问题（NOI93）：
对一个不存在回路的有向图，编程求出途经结点数最多的一条路径。有向图存放在一个文本文件中，第0行为一个数字，为该图的结点总数N，其下还有N行，每行有N个非0即1的数字。若第i行第j列的数字为1，则表示结点i到结点j存在由i指向j的边，否则该数为0。
2、删数问题的源程序：
输入数据：一个高精度正整数N，所删除的数字个数S。
输出数据：去掉的数字的位置和组成的新的正整数。
Program Delete_digit;
Var n:string;{n是由键盘输入的高精度正整数}
s,a,b,c:byte;{s是所要删除的数字的个数}
data:array[1..200] of 0..9; {记录删除的数字所在位置}
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; {记录所删除的数字的位置}
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、最优乘车问题
输入数据：输入文件INPUT.TXT。文件的第行是一个数字M（1100）表示开通了M条单向巴士线路，第2行是一个数字N（1500），表示共有N个车站。从第3行到第M+2行依次给出了第一条到第M条巴士线路的信息。其中第i+2行给出的是第i条巴士线路的信息，从左至右依次按行行驶顺序给出了该线路上的所有站点，相邻两个站号之间用一个空格隔开。
输出数据：输出文件是OUTPUT.TXT。文件只有一行，为最少换车次数（在0，1，，M-1中取值），0表示不需换车即可达到。如果无法乘车达到S公园，则输出NO。
Program Travel;
var m:1..100; {m为开通的单向巴士线路数}
n:1..500; {n为车站总数}
result:array[1..501] of -1..100; {到某车站的最少换车数}
num:array[1..500,1..50] of 1..500; {从某车站可达的所有车站序列}
sum:array[1..500] of 0..50; {从某车站可达的车站总数}
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]
writeln(result[n]);{到达S公园的最少换车次数}
end;
begin
Init;
end.
4、最佳游览路线问题
输入数据：输入文件是INPUT.TXT。文件的第一行是两个整数M和N，之间用一个空格符隔开，M表示有多少条旅游街（1100），N表示有多少条林荫道（120000）。接下里的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。
输出文件：输出文件是 OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最佳浏览路线的总分值。
Program Tour;
var m,n:integer; {M为旅游街数，N为林荫道数}
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 cdata[b] then data[b]:=c; {读取每一段旅游街的分值，并选择}
end; {到目前位置所在列的最大分值记入数组data}
close(f1);
end;
procedure Done;
var a,sum,result,c:integer;
f2:text;
begin
result:=0;
sum:=0;
a:=0;
while (an) do
begin
inc(a); {从数组的第一个数据开始累加，将累加所}
sum:=sum+data[a]; {得到的最大分值记入result}
if sumresult then result:=sum;
if sum0 then sum:=0; {若当前累加值为负数，则从当前状态起从新}
end; {累加}
assign(f2,'output.txt');
rewrite(f2);
writeln(f2,result);
close(f2);
end;
begin
Init;
Done;
end.
【信息学联赛知识：贪心策略的特点与在信息学竞赛中的应用】相关文章：
[标签：竞赛联赛,竞赛]
江苏：2019年普通高校运动训练、武术与民族传统体育专业招生文化考试即将开始
浙江：2019年普通高校招生体育专业特招生和高水平运动队体育专项测试考点和时间安排
体育总局科教司关于做好2019年体育单招考务工作有关事宜的通知
新疆：2019年普通高等学校运动训练、武术与民族传统体育专业报名3月1日开始
张雪峰高考志愿填报指南 第28集 高考志愿分析，材料科学与工程专业，就业很一般，建议慎重选择
amc传媒音乐影像 第一季 第600集 高中校长演唱《记忆花园》为高考学子助力打气
探秘历史 第二季 第233集 考英语用来睡觉，结果仍是高考状元，如今她怎么样了？
爆笑班主任 第一季 第220集 高考前最后一只视频，山东王老师揭秘高考的秘密
美术联考用纸上海考试模拟试卷纸高考统考纸 4k水粉纸素描纸 速写纸卡纸美术模拟测试试卷纸 美术考试专用纸
2019全国高考志愿填报攻略 第50集 天津市高考历史三年本科录取排名
沈阳音乐学院郎亦农教授的女高音高考曲目解析课程 第1集 沈阳音乐学院郎亦农为你讲解女高音高考曲目
