资源描述：
《USACO上面的动态规划题目.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、水题6题目名称修理牛棚数字金字塔集合最长前缀奶牛家谱程序名barn1numtrisubsetprefixnocows时间限制1s1s1s1s1s空间限制16M16M16M16M16M题目类型传统传统传统传统传统来源USACOUSACOUSACOUSACOUSACOSection1.3Section1.5Section2.2Section2.3Section2.3题目名称货币系统总分邮票商店购物家的范围程序名moneyinflatestampsshoppingrange时间限制1s1s1s1s1s空间限制16M16M16M16M16M题
2、目类型传统传统传统传统传统来源USACOUSACOUSACOUSACOUSACOSection2.3Section3.1Section3.1Section3.3Section3.3题目名称“破锣摇麦香牛块逢低吸纳巨大的牛棚周游加拿滚”乐队大程序名rockersnuggetsbuylowbigbrntour时间限制1s1s1s1s1s空间限制16M16M16M16M16M题目类型传统传统传统传统传统来源USACOUSACOUSACOUSACOUSACOSection3.4Section4.1Section4.3Section5.3Sec
3、tion5.4题目名称字符识别邮政货车矩形牛棚程序名charvansrectbarn时间限制1s1s1s提示：注意颜色深浅空间限制16M16M16M题目类型传统传统传统与难度之间的联系来源USACOUSACOUSACOSection5.4Section6.1Section6.1BarnRepair(Section1.3)修理牛棚译bytimgreen在一个暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。好在许多牛正在度假，所以牛棚没有住满。剩下的牛一个紧挨着另一个被排成一行来过夜。有些牛棚里有牛，有些没有。所有的牛棚有相同的宽度。自门
4、遗失以后,农民约翰很快在牛棚之前竖立起新的木板。他的新木材供应者将会供应他任何他想要的长度,但是供应者只能提供有限数目的木板。农民约翰想将他购买的木板总长度减到最少。给出M(1<=M<=50),可能买到的木板最大的数目;S(1<=S<=200),牛棚的总数;C(1<=C<=S)牛棚里牛的数目,和牛所在的牛棚的编号stall_number(1<=stall_number<=S),计算拦住所有有牛的牛棚所需木板的最小总长度。输出所需木板的最小总长度作为的答案。PROGRAMNAME:barn1INPUTFORMAT第1行:M，S和C(用空
5、格分开)第2到C+1行:每行包含一个整数，表示牛所占的牛棚的编号。SAMPLEINPUT(filebarn1.in)4501834681415161721252627303140414243OUTPUTFORMAT单独的一行包含一个整数表示所需木板的最小总长度。SAMPLEOUTPUT(filebarn1.out)25[一种最优的安排是用板拦住牛棚3-8,14-21,25-31,40-43.]NumberTriangles(Section1.5)数字金字塔译bytimgreen考虑在下面被显示的数字金字塔。写一个程序来计算从最高点开始
6、在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。738810274445265在上面的样例中,从7到3到8到7到5的路径产生了最大和:30PROGRAMNAME:numtriINPUTFORMAT第一个行包含R(1<=R<=1000),表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。SAMPLEINPUT(filenumtri.in)5738810274445265OUTPUTFORMAT单独的一行包含那个可能得到的最大的和。SAMPLEOUTP
7、UT(filenumtri.out)30SubsetSums(Section2.2)集合对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：•{3}and{1,2}这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:•{1,6,7}and{2,3,4,5}{注1+6+7=2+3+4+5}•{2
8、,5,7}and{1,3,4,6}•{3,4,7}and{1,2,5,6}•{1,2,4,7}and{3,5,6}给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。PRO
