动态规划NOIP的题目

本文格式为Word版，下载可任意编辑——动态规划NOIP的题目DPProblemSet

顺序对齐

源程序名ALIGN.???(PAS,C,CPP)可执行文件名ALIGN.EXE输入文件名ALIGN.IN输出文件名ALIGN.OUT

考虑两个字符串右对齐的最正确解法。例如，有一个右对齐方案中字符串是AADDEFGGHC和ADCDEGH。

AAD_DEFGGHCADCDE__GH_

每一个数值匹配的位置值2分，一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数，在上述给定的例子中，6个位置(A,D,D,E,G,H)匹配，三段空格，所以得分2*6+(-1)*3=9，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。

请你写个程序找出最正确右对齐方案。输入

输入文件包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。输出

一行，为最正确对齐的得分。样例ALIGN.IN

AADDEFGGHCADCDEGH

ALIGN.OUT9

_______________________________________________________________________________

任务安排

源程序名BATCH.???(PAS,C,CPP)可执行文件名BATCH.EXE输入文件名BATCH.IN输出文件名BATCH.OUT

N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。

-1-

DPProblemSet

例如：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(1DPProblemSet

输出

输出文件仅一行。假使凑不齐K+3双，输出-1，否则输出长度差平方和的最小值。样例CHOP.IN101

112333461020

CHOP.OUT5说明

第一双11其次双23第三双33第四双46

(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5

_______________________________________________________________________________

护卫队

源程序名CONVOY.???(PAS,C,CPP)可执行文件名CONVOY.EXE输入文件名CONVOY.IN输出文件名CONVOY.OUT

护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。由于街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。问题要求计算出全部护卫车队通过该桥所需的最短时间值。输入

输入文件第一行包含三个正整数(用空格隔开)，第一个整数表示该桥所能承受的最大载重量(用吨表示)；其次个整数表示该桥的长度(用千米表示)；第三个整数表示该护卫队中车辆的总数(nDPProblemSet

（railway.exe）

从Ekaterinburg到Sverdlovsk的火车线路上有若干个站点。这条线路可以近似的表示为一条线段，火车站就是线段上的点。线路始于Ekaterinburg，终究Sverdlovsk。Ekaterinburg被标号为1，Sverdlovsk被标