动态规划部分练习(1).docx

动态规划部分练习(一)
(普及组不作要求)
顺序对齐
(  )
源程序名 ALIGN.??? ( PAS,C,CPP)
可执行文件名
输入文件名
输出文件名
[ 问题描述 ] :
考虑两个字符串右对齐的最佳解法。例如,有一个右对齐方案中字符串是 AADDEFGGHC
。
和 ADCDEGH
AAD_DEFGGHC
ADCDE__GH_
每一个数值匹配的位置值 2 分,一段连续的空格值 -1 分。所以总分是匹配点的 2 倍减
去连续空格的段数,在上述给定的例子中, 6 个位置( A,D,D,E,G,H)匹配,三段空格,
所以得分 2*6+(-1)*3=9 ,注意,我们并不处罚左边的不匹配位置。若匹配的位置是两个不
同的字符,则既不得分也不失分。
请你写个程序找出最佳右对齐方案。
[ 输入格式 ] :
输入文件包含两行,每行一个字符串,最长 50 个字符。字符全部是大字字母。
[ 输出格式 ] :
一行,为最佳对齐的得分。
[ 样例输入 ] :

AADDEFGGHC
ADCDEGH
[ 样例输出 ] :
9
-1-
任务安排
(  )
源程序名 BATCH.???( PAS,C,CPP)
可执行文件名
输入文件名
输出文件名
[ 问题描述 ] :
i
N 个任务排成一个序列在一台机器上等待完成(顺序不得改变) ,这 N 个任务被分成若
干批, 每批包含相邻的若干任务。从时刻 0 开始, 这些任务被分批加工,第 i 个任务单独完
成所需的时间是 T 。在每批任务开始前,机器需要启动时间 S,而完成这批任务所需的时间
是各个任务需要时间的总和(同一批任务将在同一时刻完成) 。每个任务的费用是它的完成
时刻乘以一个费用系数 Fi 。请确定一个分组方案,使得总费用最小。
例如: S=1; T={1 , 3, 4, 2, 1} ;F={3 , 2,3, 3, 4} 。如果分组方案是 {1 , 2} 、 {3} 、
{4 , 5} ,则完成时间分别为 {5 , 5, 10, 14 ,14} ,费用 C={15 ,10 , 30, 42, 56} ,总费用
就是 153。
[ 输入格式 ] :
第一行是 N( 1<=N<=5000)。
第二行是 S( 0<=S<=50)。
i
下面 N 行每行有一对数,分别为 Ti 和 F ,均为不大于 100 的正整数,表示第 i 个任务
单独完成所需的时间是 Ti 及其费用系数 Fi 。
[ 输出格式 ] :
一个数,最小的总费用。
[ 样例输入 ] :
:
5
1
13
32
43
23
14
[ 样例输出 ] :
:

153
-2-
最大的算式
( )
源程序名 BIGEXP.???( PAS,C,CPP)
可执行文件名
输入文件名
输出文件名
[ 问题描述 ] :
题目很简单,给出 N 个数字