文档介绍：动态规划测试卷
命题人:柯桥中学
程序名
输入文件
输出文件
时限
内存
Problem 1
1

1s
64M
Problem 2
2

1s
64M
Problem 3
3

1s
64M
Problem 4
4

1s
64M
Problem 1 活蹦乱跳的香穗子
香穗子在田野上调蘑菇!她跳啊跳,发现自己很无聊,于是她想了一个有趣的事情,每个格子最多只能经过1次,且每个格子都有其价值
跳的规则是这样的,香穗子可以向上下左右四个方向跳到相邻的格子,并且她只能往价值更高(这里是严格的大于)的格子跳.
香穗子可以从任意的格子出发,在任意的格子结束,
那么她最多能跳几次?
输入:
第一行n,m,表示田野的长和宽
接下来n行,每行m个数,表示该格的价值
输出:
一个数,表示最多跳得次数
Sample Input
2 2
2 5
-1 3
Sample Output
2
数据范围:
n,m<=100
答案保正小于Maxlongint
Problem 2 可爱迷人的香穗子
香穗子正准备参加一个晚会!现在她准备好好打扮一下,她准备戴上耳环,手镯,项链..等等一些装饰品,这里要说明的是,香穗子不是花瓶….
香穗子最多能承受W的重量,每个装饰品也有各自的重量和美观值
现在香穗子要怎么打扮,美观值的和最大
输入:
第一行两个数,w,n
接下来n行,每行两个数,表示物品的信息,第一个数是物品的重量,第二个数是物品的美观值
输出:
表示香穗子最多能得到的最大美观值和
Sample Input
10 2
7 8
8 7
Sample Output
8
数据范围:
n<=100,w<=10000
答案保正小于Maxlongint
Problem 3 Cyh和香穗子
话说,Cyh和香穗子是好朋友,一天他们在fzsz迷路了….Cyh在地点1,,所以Cyh准备去n地给香穗子带路.
fzsz是个奇怪的地方,它由n地点组成,并且任意两个地点A,B满足要么A能到B,要么B能到A,要么都不能互相到达,一定不存在A和B都能互相到达.
现在Cyh希望快点到达n地
输入:
第一