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個騎士需要被擺到棋盤上去。那么使所有騎士互不攻擊的擺放方式一共有多少種呢？

輸入數