来自：查字典高考网 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 山西一高中班主任带学生骑行1800公里去上海
amc传媒音乐影像 第一季 第600集 高中校长演唱《记忆花园》为高考学子助力打气
高考阅卷名师给考生的高考作文密训课 第3集 高考作文审题实操方法精讲（一）
北京新闻 2019 5.9万余北京考生今日高考 语文试题鼓励创造性阅读与表达
高考体育四项生的日常训练——深蹲移动跳：发展膝关节，踝关节力量。
爆笑班主任 第一季 第221集 高考结束学生有多疯狂？山东王老师疯狂吐槽
探秘历史 第二季 第211集 此人高考数学考了0分，因作文写3句话被重点大学录取
一边扔试卷一边玩摇滚？这个学校的高考减压方式，真是帅到没朋友
张雪峰高考志愿填报指南 第28集 高考志愿分析，材料科学与工程专业，就业很一般，建议慎重选择
高考阅卷名师给考生的高考作文密训课 第4集 高考作文审题实操方法精讲（二）
探秘历史 第二季 第233集 考英语用来睡觉，结果仍是高考状元，如今她怎么样了？
你高考成绩高吗？这道题目怎能成立？高难度奥数，能不能把你难住
