26基本算法之动态规划

《26基本算法之动态规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2.6基本算法之动态规划01()1775:采药总时间限制：1000ms内存限制：65536kB描述辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子,这个山洞里有一些不同的草药，采每一株都需要一些时间，毎一株也有它自身的价值。我会给你一段吋间，在这段吋间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？输入输入的第一行有两个整数T(

2、1<=T<=1000)和M(1<=M〈二100),T代表总共能够用來采药的时间，M代表山洞里的草药的数目。接下來的M行每行包括两个在1至U100Z间(包括1和100)的的整数，分别表示采摘某株草药的时间和这株草药的价值。输击输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。样例输入7037110069112样例输出3来源[944:吃糖果总时间限制：1000ms内存限制：65536kB描述名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有N块巧克力，20>N>0）o妈妈告诉名名每天可以吃一

3、块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。例如：如果N=l,则名名第1天就吃掉它，共有1种方案；如果N=2,则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；如果N=3,则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案；如果N=4,则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。现在给定N,请你写程序求出名名吃巧克力的方案数目。输寿入只有1行，即整数N。输出输出只有1行，即名名吃巧克力的方案数。样例输入样例输

4、出6252:带通配符的字符串匹配1!总时间限制：1000ms内存限制：65536kB描述通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。通配符有问号(？)和星号(*)等，其中，''?〃可以代替一个字符，而〃可以代替零个或多个字符。你的任务是，给出一个带有通配符的字符串和一个不带通配符的字符串，判断他们是否能够匹配。例如，17456可以匹配12456、13456、"456,但是却不能够匹配23456、laa456；2*77?8可以匹酉己24457798、237708、27798o输入输入

5、有两行，每行为一个不超过20个字符的字符串，第一行带通配符，第二行不带通配符输出如果两者可以匹配，就输出''matchecT,否则输出''notmatched"样例输入1*456?样例输出matched666:放苹果总时间限制：1000ms内存限制：65536kB描述把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？(用K表示)5,1,1和1,5,1是同一种分法。输入第一行是测试数据的数目t(0<=t<=20)o以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10o输出对输入的每组数据M和N,用一

6、行输出相应的Ko样例输入173样例输出7614:最低通行费总时间限制：1000ms内存限制：65536kB描述一个商人穿过一个N*N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。输入第一行是一个整数，表示正方形的宽度N(1<=N<10

7、0)；后面N行，每行N个不大于100的整数，为网格上每个小方格的费用。输出至少需要的费用。样例输入51468102571517689182010111219212023252933样例输出109提示样例中，最小值为109=1+2+5+7+9+12+19+21+33o7624:山区建小学总时间限制：1000ms内存限制：65536kB描述政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中,0

8、府又决定从m个村中选择n个村建小学（设Ovnv=mv500）。请根据给定的m.n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小,计算最小值。输