动态规划习题集全.doc

动态规划专题训练 护卫队 【问题描述】 护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。 问题要求计算出全部护卫车队通过该桥所需的最短时间值。 【输入】 【输】 【输入输出样例】 输入： 100 5 10 40 25 50 20 50 20 70 10 12 50 9 70 49 30 38 25 27 50 19 70 输入： 75.0 DOLLARS 【问题描述】 在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。 【输入】0）。 第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。 【输】5 400 300 500 300 250 输入： 266.66 样例解释： Day 1 … changing 100.0000 美元 = 400.0000 马克 Day 2 … changing 400.0000 马克 = 133.3333 美元 Day 3 … changing 133.3333 美元 = 666.6666 马克 Day 5 … changing 666.6666 马克 = 266.6666 美元 胖男孩 【问题描述】 麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。 每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。 当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。 请编写一个程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。 【输入】 【输】 【输入输出样例】 输入： cecqbhvaiaedpibaluk cabegviapcihlaaugck adceevfdadaepcialaukd 输出： cevapiluk 钓鱼 【问题描述】 约翰是个垂钓谜，星期天他决定外出钓鱼h（1=h=16）小时，约翰家附近共有n（2=n=25）个池塘，这些池塘分布在一条直线上，约翰将这些池塘按离家的距离编上号，依次为L1，L2，…，Ln，约翰家门外就是第一个池塘，所以他到第一个池塘是不用花时间的，约翰可以任选若干个池塘垂钓，并且在每个池塘他都可以呆上任意长的时间，但呆的时间必须为5分钟的倍数，（5分钟为一个单位时间），已知从池塘Li到池塘Li+1要化去约翰ti个单位时间，每个池塘的上鱼率预先也是已知的，池塘Li在第一个单位时间内能钓到的鱼为Fi（0=Fi=100），并且每过一个单位时间在单位时间内能钓到的鱼将减少一个常数di（0=di=100）。 现在请你编一个程序来计算约翰最多能钓到多少鱼。 【输入】i=1，2，…，n）。 第四行为n个用空格隔开的整数，表示di（i=1，2，…，n）。 第五行为n-1个用空格隔开的整数，表示ti（i=1，2，…，n-1）。 【输】 【输入输出样例】 输入： 2 1 10 1 2 5 2 输出： 31 数学作业 【问题描述】 数学竞赛刚刚结束，据说题目很难，不过信息学里面的数学题也不容易哦，题目描述很简单：求：方程x1+2x2+…+nxn=m的所有非负整数解（x1,x2,…,xn）的个数。例如，方程：x1+2x2+3x3+4x4+5x5=5有7组解：（5,0,0,0,0）、（3,1,0 ,0,0）、…、（0,0,0,0,1）。 运用你的数学思维加上强大的信息学能力，试试解决它吧！ 【输入数据】 2个整数n，m 【输出数据】 方程非负整数解的个数ans，如果解超过10^9，只需输出ans mod 10^9。 【输入样例】 5 5 【输出样例】 7 【数据范围】 1≤n≤5000；0≤m≤5000。 圆桌会议 【问题描述】 晚会结束的第二天，学校决定请获奖的同学开一个圆桌会议。假设有N个人顺时针围在一圆桌上开会，不过他们对身