动态规划练习题合集(Dp-合集)

5/5动态规划练习题合集(Dp-合集)一、关键子工程（project.c/cpp/pas）

在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为1、2、……、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有这种特征的子工程称为关键子工程，因此第二个任务就是找出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设：

（1）根据预算，每一个子工程都有一个完成时间。

（2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。

（3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也既同时施工的子工程个数不受限制。

（4）整个工程的完成是指：所有子工程的完成。

其中，表格中第I+1行J+2列的值如为0表示“子工程I”可以在“子工程J”没完成前施工，为1表示“子工程I”必须在“子工程J”完成后才能施工。上述工程最快完成时间为14天，其中子工程1、3、4、5为关键子工程。

又例如，有五个子工程的工程规划表：

上述的子工程划分不合理，因为无法安排子工程1，3，4的施工。

输入数据：

第1行为N，N是子工程的总个数，N≤200。

第2行为N个正整数，分别代表子工程1、2、……、N的完成时间。

第3行到N+2行，每行有N-1个0或1。其中的第I+2行的这些0，1，分别表示“子工程I”与子工程1、2、…、I-1、I+1、…N的依赖关系，（I=1、2、……、N）。每行数据之间均用一个空格分开。

输出数据：

如子工程划分不合理，则输出-1；

如子工程划分合理，则用两行输出：第1行为整个工程最少的完成时间。第2行为按由小到大顺序输出所有关键子工程的编号。

样例：

输入文件名：project.in

5

541272

0000

0000

0000

1100

1111

输出文件名：project.out

14

1345

二、机器分配（machine.c/cpp/pas）

某总公司拥有高效生产设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为总公司提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。

分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。其中M1）个部分，使这N个部分的乘积最大。N、M从键盘输入，输出最大值及一种划分方式。

输入数据：

第一行一个正整数T(T，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。

对给定的两个字符序列，求出他们最长的公共子序列。

输入数据：

第1行为第1个字符序列，都是大写字母组成，以”.”结束。长度小于5000。

第2行为第2个字符序列，都是大写字母组成，以”.”结束，长度小于5000。

输出数据：

输出上述两个最长公共自序列的长度。

样例：

lcs.in

ABCBDAB.

BACBBD.

lcs.out

4

卡车更新问题（文件名：truck.pas/c/cpp）

某人购置了一辆新卡车,从事个体运输业务.给定以下各有关数据:R[t],t=0，1,2,...,k,表示已使用过t年的卡车,再工作一年所得的运费,它随t的增加而减少,k(k≤20)年后卡车已无使用价值.

U[t]：t=0，1,...,k,表示已使用过t年的卡车,再工作一年所需的维修费,它随t的增加而增加.

C[t],t=0，1,2,...,k,表示已使用过t年的旧卡车,卖掉旧车,买进新车,所需的净费用,它随t的增加而增加.以上各数据均为实型,单位为"万元".

设某卡车已使用过t年,

①如果继续使用,则第t+1年回收额为R[t]-U[t],

②如果卖掉旧车,买进新车,则第t+1年回收额为R[0]-U[0]-C[t].

该运输户从某年初购车日起,计划工作N(N，它的最长上升子序列为，但如果限制一定要包含第2个元素，那么满足此要求的最长上升子序列就只能是了。

输入数据

第一行为两个整数N,K，如上所述。

接下来是N个整数，描述一个序列。

输出数据

请输出两个整数，即包含第K个元素的最长上升子序列长度。

样例

输入

86

65158170299300155207389

输出

4

数据范围

对于所有的数据，满足0<n<=200000，0<k<=n

最短回文串（palindrome.pas/c/cpp）

如果一个字符串正过来读和倒过来读是一样的，那么这个字符串就被称作回文串。例如abcdcba，abcddbca就是回文串，而abcdabcd不是。

你要解决的问题是：对于任意一个字符串，输出将这个字符串变为回文串需要插入的最少字符个数，比如，ab3bd只需要插入2个字符就可以变为一个回文串。

输入数据

第一行是一个整数N

第二行是一个长度为N字符串S

输出数据

一行一个整数，表示将S变为回文串需要插入的最小字符个数

样例

输入

5

ab3bd

输出

2

数据范围

对于所有数据，0<n<=5000

硬木地板(floor.pas/c/cpp)

举行计算机科学家盛宴的大厅的地板为M×N(1<=M<=9,1<=N<=9)的矩形。现在必须要铺上硬木地板砖。可以使用的地板砖形状有两种：

1)2×1的矩形砖

2)2×2中去掉一个1×1的角形砖

你需要计算用这些砖铺满地板共有多少种不同的方案。

注意：必须盖满，地板砖数量足够多，不能存在同时被多个板砖覆盖的部分。

输入数据

包含M和N。

输出数据

输出方案总数，如果不可能那么输出0。

样例

输入:floor.in

23

输出:floor.out

5

通向自由的钥匙(key.pas/c/cpp)

通向自由的钥匙被放n个房间里，这n个房间由n-1条走廊连接。但是每个房间里都有特别的保护魔法，在它的作用下，我无法通过这个房间，也无法取得其中的钥匙。虽然我可以通过消耗能量来破坏房间里的魔法，但是我的能量是有限的。那么，如果我最先站在1号房间（1号房间的保护魔法依然是有效的，也就是，如果不耗费能量，我无法通过1号房间，也无法取得房间中的钥匙），如果我拥有的能量为P，我最多能取得多少钥匙？

输入数据

第一行包含两个非负整数，第一个为N，第二个为P。

接下来n行，按1~n的顺序描述了每个房间。第i+1行包含两个非负整数cost和keys，分别为第i件房取消魔法需要耗费的能量和房间内钥匙的数量。

接下来n-1行，每行两个非负整数x,y，表示x号房间和y号是连通的。

输出数据

一行一个整数，表示取得钥匙的最大值。

样例

输入:key.in

55

12

11

11

23

34

12

13

24

25

输出:key.out

7

数据范围

对于20%的测试数据，有n<=20

对于30%的测试数据，有n<=30

对于所有测试数据，有p,n<=100,cost<=Maxint,keys<=Maxint

三角蛋糕(trigon.pas/c/cpp)

XP在机房里放了一块正三角形的大蛋糕，但是第二天他发现蛋糕被老鼠咬坏了。

XP不想让蛋糕白白的被浪费，于是他把蛋糕分割成了一个个的小正三角形（如上图所示）。黑色的小正三角形表示老鼠把那一块咬坏了。XP想要切出一块最大的没被老鼠咬坏正三角形的蛋糕，可是最大的三角形有多大呢?

输入数据

第一行，一个整数N，表示XP把蛋糕纵向划分为N行。

接下来的N行，第i行包括了(n-i)*2+1个有效字符。“-”表示这块蛋糕是好的，“#”表示这块蛋糕被咬坏了。为了保持三角形的形状，输入文件中会出现空格。

输出数据

一行一个整数，表示最大的三角形包括的小三角形数。

样例

输入:trigon.in

5

#-###

#-

#-

-#-

-

输出:trigon.out

9

数据范围

对于30%的数据，满足n≤5

对于所有的测试数据，满足n≤100。

骑士（knight.pas/c/cpp）

国际象棋中骑士的移动规则和中国象棋中的马是类似的，它先沿着一个方向移动两格，再沿着与刚才移动方向垂直的方向移动一格。路径上的棋子并不会影响骑士的移动，但是如果一个骑士走到了一个放有棋子的格子，它就会攻击那个棋子。现在有一个n*n的棋盘，有k个骑士需要被摆到棋盘上去。那么使所有骑士互不攻击的摆放方式一共有多少种呢？

输入数