种树 源程序名 trees.???（pas, c, cpp） 可执行文件名 trees.exe 输入文件名 trees.in 输出文件名 trees.out 【问题描述】 一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。 写一个程序完成以下工作： * 从trees.in读入数据
* 计算最少要种树的数量和位置 * 把结果写到trees.out 【输入】
第一行包含数据N，区域的个数(0 下面的H行描述居民们的需要：B E T，0 输出文件第一行写有树的数目，下面的行包括所有树的位置，相邻两数之间用一个空格隔开。 【样例】 trees.in trees.out 9 5 4 1 4 5 8 9 1 4 2 4 6 2 8 9 2 3 5 2 Type point=record b,e,t:integer; end; Var tree:array[1..30000]of boolean; a:array[1..5000]of point; tmp:point; h,n,i,j,k,min:integer; Begin readln(n); readln(h); for i:=1 to h do readln(a[i].b,a[i].e,a[i].t); for i:=1 to h-1 do for j:=i+1 to h do if a[i].e>a[j].e then begin tmp:=a[i];a[i]:=a[j];a[j]:=tmp;end; fillchar(tree,sizeof(tree),false); for i:=1 to h do begin k:=0;for j:=a[i].b to a[i].e do if tree[j] then inc(k); 原先这个区间有多少棵树 if k min:=0; for i:=1 to n do if tree[i] then inc(min); writeln(min); 计算并输出最少种树数，此答案唯一 for i:=1 to n do if tree[i] then write(i,' '); 输出方案，本题存在明显的一题多解，方案可不唯一 End. n总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M<=15，N<=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。n数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。 很多书都拿这题当动态规划的入门例题来说，因为本题具有明显的无后效性，这个机器分给谁与那个机器分给谁没有关系，顺着这个思路往下想就行了。 Program 机器分配; Var a:array[1..15,1..10]of longword; max,s:qword; m,n,i,j:integer; Begin readln(m,n); for i:=1 to m do for j:=1 to n do read(a[i,j]); for i:=1 to m do begin s:=1; for j:=2 to n do if a[i,j]>a[i,s] then s:=j; inc(max,a[i,s]); end; writeln(max); End. n在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。问：最多能拾多少垃圾。在最多的情况下，有多少种方案？请举出一种方案来。n数据范围:n<=100,m<=100 同过河卒的方法差不多，f[i,j]只有可能是从f[i-1,j]或f[i,j-1]两格得到的，所以只要看两格那个大，就从这一格走过来，如果相等，从哪个走过来都一样。至于方案，也是跟着max加，如果两格最大值相等，就把两格方案都加上。 Program robots; Var f,max:array[0..100,0..100]of longword; c:array[1..100,1..100]of boolean; n,m,i,j,x:longword; Begin readln(n,m); for i:=1 to n do for j:=1 to m do begin read(x); if x=1 then c[i,j]:=true else c[i,j]:=false; end; f[1,1]:=1; for i:=1 to n do for j:=1 to m do begin if max[i-1,j]=max[i,j-1] then begin inc(f[i,j],f[i-1,j]+f[i,j-1]); max[i,j]:=max[i-1,j]; end; if max[i-1,j]>max[i,j-1] then begin f[i,j]:=f[i-1,j]; max[i,j]:=max[i-1,j]; end; if max[i-1,j] f[i,j]:=f[i,j-1]; max[i,j]:=max[i,j-1]; end; if c[i,j] then inc(max[i,j]); end; writeln(max[n,m],' ',f[n,m]); End.
