递归和深搜的简单练习题目

《递归和深搜的简单练习题目》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、解题报告2011年1月26日总结概括读题时间：8：38-8：50；时间：8：50-11：35提交次数：4难度：★★★★☆总体评价：递推，我的弱项第一题题意描述：超级书架2[NealWu,2007]【问题描述】FarmerJohn最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。所有N(1<=N<=20)头奶牛都有一个确定的身高H_i(1<=H_i<=1,000,000-好高的奶牛>_<)。设所有奶牛身高的和为S。书架的高度为B，并且保证1<=B<=S。为了够到比最高的那头奶牛还要高的

2、书架顶，奶牛们不得不象演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。塔叠得越高便越不稳定，于是奶牛们希望找到一种方案，使得叠出的塔在高度不小于书架高度的情况下，高度尽可能小。你也可以猜到你的任务了：写一个程序，计算奶牛们叠成的塔在满足要求的情况下，最少要比书架高多少。程序名:shelf2【输入格式】*第1行:2个用空格隔开的整数：N和B*第2..N+1行:第i+1行是1个整数：H_i【输入样例】(shelf2.in):51631356【输出格式】*第1行

3、:输出1个非负整数，即奶牛们叠成的塔最少比书架高的高度【输出样例】(shelf2.out):1输出说明:我们选用奶牛1、3、4、5叠成塔，她们的总高度为3+3+5+6=17。任何方案都无法叠出高度为16的塔，于是答案为1。思路我的思路：贪心，从打到小进行排序，找出一个数，使前面的所有数加上这个数大于B，不加这个数小于B，然后再进行查找，但是此方法必然不过。结果：过了7组，很给力呀正确的思路：应该是深搜代码实现时间：8：55-9：11跟踪调试：把dd（0）,写成dd(1)了完整代码programex01;constinf='shelf2.in';ouf='shelf2.

4、out';varn,b,i,j,tot,l,r,min:longint;h:array[1..30]oflongint;f:array[1..30]ofboolean;proceduredd(k:longint);vari:longint;beginifk>nthenexit;fori:=k+1tondoiff[i]thenbegintot:=tot+h[i];iftot>=bthenbeginiftot-b

5、ot-h[i];end;end;beginassign(input,inf);reset(input);assign(output,ouf);rewrite(output);fillchar(f,sizeof(f),true);readln(n,b);fori:=1tondoreadln(h[i]);min:=maxlongint;fori:=1tondo//先找出来比b大的数，进行标记和比较beginifh[i]>bthenbeginifh[i]-b

6、里面的写的是dd（i），所以果断不过writeln(min);close(input);close(output);end.最终评测设计数据：无提交次数：2第一次：贪心，7组评价：简单的搜索，只用判断两个，用或者不用第二题题意描述：flowerb【题目描述】 农夫John出去砍伐，让N头牛在草地上吃草。当他回来时吃惊的看到这些牛全部都跑到花园里在吃他的美丽花朵。他立即去把每头牛赶回它的牛栏。 i号牛每分钟要吃掉D_i朵花，距离自己的栏地要T_i分钟路程。不幸的是John每次只能赶一头牛回栏，再回到花园。请问这些牛最少要吃掉多少朵花？ 【数据范围】 2<=N<=100,

7、000 1<=T_i<=2,000,000 1<=D_i<=100【输入文件flowerb.in】  第一行一个数N。  下面N行，每行两个数T_iD_i，表示第i头牛的数据。【输出文件flowerb.out】 一个整数，最少吃掉的花朵数。【样例输入】6312523324116【样例输出】86【说明】最好方案：赶回牛的次序为6,2,3,4,1,5思路我的思路：贪心，多关键字排序，以D为第一关键字进行降序排列，以T为第二关键字进行升序排列，刚开始一直算不出来86，后来发现农夫在把牛赶出花园后返回来也需要同样多的时间正确思路：用d/t进行权值的排序代码实