入門-動(dòng)態(tài)規(guī)劃

• 1. [分梨](http://acm.zzu.edu.cn/problem.php?id=1163)
• • • 解析 遞歸分配
    • AC
• 2. 最大公共子序列
• 3. [最大子段和](http://acm.hdu.edu.cn/showproblem.php?pid=1003)
• • • 解析
    • AC
• 4. [最大子陣和](http://acm.hdu.edu.cn/showproblem.php?pid=1081)
• • • 解析
    • AC
• 5. [母牛的故事](http://acm.hdu.edu.cn/showproblem.php?pid=2018)
• • • 解析
    • AC
• 6. [數(shù)塔](http://acm.hdu.edu.cn/showproblem.php?pid=2084)
• • • 解析
    • AC
• 7. [一只小蜜蜂](http://acm.hdu.edu.cn/showproblem.php?pid=2044)
• • • 解析
    • AC
• 8. [折線分割平面](http://acm.hdu.edu.cn/showproblem.php?pid=2050)
• • • 解析
    • AC
• 9. [獻(xiàn)給杭電五十周年校慶的禮物](http://acm.hdu.edu.cn/showproblem.php?pid=1290)
• • • 解析
    • AC

1. 分梨

題目描述
小明非常喜歡吃梨，有一天他得到了ACMCLUB送給他的一筐梨子。由于他比較仗義，就打算把梨子分給好朋友們吃?，F(xiàn)在他要把M個(gè)梨子放到N個(gè)盤子里面（我們?cè)试S有的盤子為空），你能告訴小明有多少種分法嗎？（請(qǐng)注意，例如有三個(gè)盤子，我們將5,1,1和1,1,5，視為同一種分法）

輸入
輸入包含多組測(cè)試樣例。每組輸入的第一行是一個(gè)整數(shù)t。
接下來(lái)t行，每行輸入兩個(gè)整數(shù)M和N，代表有M個(gè)梨和N個(gè)盤子。（M和N均大于等于0）

輸出
對(duì)于每對(duì)輸入的M和N，輸出有多少種方法。

樣例輸入

1
7 3

樣例輸出

8

解析 遞歸分配

M個(gè)梨， N個(gè)盤子的分法 dp(m, n){if (只有一個(gè)盤子 || 沒(méi)有梨)只有一種分法；if (盤子N比梨M多)則最多用M個(gè)盤子, dp(m,n) = dp(m,m)；else 如果每個(gè)至少一個(gè)梨， 則dp(m-n, n)如果有一個(gè)盤子為空， 則dp(m, n-1)dp(m, n) = dp(m, n-1) + dp(m-n, n)}

AC

#include<stdio.h> int c(int x,int y) { if(y == 1 || x == 0)return 1;if(x<y) return c(x,x);elsereturn c(x,y-1)+c(x-y,y); }int main() {int t,n,m;while(scanf("%d",&t)!=EOF){while(t--){scanf("%d%d",&m,&n);printf("%d\n",c(m,n));}} return 0; }

2. 最大公共子序列

見之前的博客

3. 最大子段和

Problem Description
Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output
For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output

Case 1:
14 1 4

Case 2:
7 1 6

解析

sum, maxsum = M[n-1] for auto m : M[]:sum = max(sum+m, m)if sum >= maxsum:maxsum = sum

AC

#include <iostream> #include <cstring>using namespace std;int M[100005], arr[100005]; int l, r; int maxSubArr(int D[], int n){int i, sum = 0, maxsum = D[n-1];l = n-1;for (i=n-1; i>=0; i--){if (sum > 0){sum = sum + D[i];}else{sum = D[i];}if (sum >= maxsum) { //If there are more than one result, output the first one.maxsum = sum;l = i;}}return maxsum; }int main(){int T, N;cin>>T;for (int t=1; t<=T; t++){cin>>N;for (int i=0; i<N; i++){cin>>M[i];}int ans = maxSubArr(M, N);cout<<"Case "<<t<<":"<<endl;int s = 0;for (int i = l; i<N; i++){s += M[i];if (s == ans){r=i;break;}}cout<<ans<<" "<<l+1<<" "<<r+1<<endl;if (t<T){cout<<endl;}}return 0;}

4. 最大子陣和

Problem Description
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.

As an example, the maximal sub-rectangle of the array:

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

is in the lower left corner:

9 2
-4 1
-1 8

and has a sum of 15.

Input
The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

Output
Output the sum of the maximal sub-rectangle.

Sample Input

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

Sample Output

15

解析

這一題可以借助上一題的思路，把求最大子陣轉(zhuǎn)化為求最大子段和，也就是變成一維情況。 (以第一行最為開始)先求第一行的最大和;將第二行數(shù)據(jù)加到第一行，再求此時(shí)的最大值;再將下一行加上去，求最大值.....; .最終得到第一列到最后一列的最大值；還要計(jì)算第二行到最后一行的最大和，第三行到最后一行的最大和；fun(){ //求最大子段和 }for i = 0 : N #第i行到j(luò)行最大子陣和# 第一次循環(huán)結(jié)束，我們得到的是第一行到第N行的N x M的最大子陣和（N是行數(shù)，M是列數(shù)，M由fun（）決定）# 第二次循環(huán)結(jié)束，我們得到的是第二行到第N行的N-1 x M的最大子陣和for j = i : N 把第j行加到array上：arry[k] = M[j][k]計(jì)算array的最大子段和：fun(array)

AC

#include <iostream> #include <cstring>using namespace std;int M[105][105], arr[105]; int maxSubArr(int D[], int n){int sum=0, maxsum=D[0];for (int i=0; i<n; i++){if (sum>0){sum = sum + D[i];}else{sum = D[i];}if (sum > maxsum) maxsum = sum;}return maxsum; }int main(){int N;while(scanf("%d", &N) != EOF){//注意輸入for (int i=0; i<N; i++){for (int j=0; j<N; j++){cin>>M[i][j];}}int maxsubrec = M[0][0];for (int i=0; i<N; i++){memset(arr, 0, sizeof(arr));for (int j=i; j<N; j++){for (int k=0; k<N; k++){arr[k] += M[j][k];}int maxsubarr = maxSubArr(arr, N);if (maxsubarr > maxsubrec) maxsubrec = maxsubarr;} }cout<<maxsubrec<<endl;}return 0;}

5. 母牛的故事

Problem Description
有一頭母牛，它每年年初生一頭小母牛。每頭小母牛從第四個(gè)年頭開始，每年年初也生一頭小母牛。請(qǐng)編程實(shí)現(xiàn)在第n年的時(shí)候，共有多少頭母牛？

Input
輸入數(shù)據(jù)由多個(gè)測(cè)試實(shí)例組成，每個(gè)測(cè)試實(shí)例占一行，包括一個(gè)整數(shù)n(0<n<55)，n的含義如題目中描述。
n=0表示輸入數(shù)據(jù)的結(jié)束，不做處理。

Output
對(duì)于每個(gè)測(cè)試實(shí)例，輸出在第n年的時(shí)候母牛的數(shù)量。
每個(gè)輸出占一行。

Sample Input

2
4
5
0

Sample Output

2
4
6

解析

f(n) = f(n-1) + f(n-3)

AC

#include<stdio.h> //遞歸 int sum(int n) {if (n <= 4) return n;else return (sum(n-1) + sum(n - 3)); } int main() {int n;while (~scanf("%d", &n) != EOF&&n!=0)printf("%d\n", sum(n));getchar();return 0; }

6. 數(shù)塔

Problem Description
在講述DP算法的時(shí)候，一個(gè)經(jīng)典的例子就是數(shù)塔問(wèn)題，它是這樣描述的：

有如下所示的數(shù)塔，要求從頂層走到底層，若每一步只能走到相鄰的結(jié)點(diǎn)，則經(jīng)過(guò)的結(jié)點(diǎn)的數(shù)字之和最大是多少？

已經(jīng)告訴你了，這是個(gè)DP的題目，你能AC嗎?

Input
輸入數(shù)據(jù)首先包括一個(gè)整數(shù)C,表示測(cè)試實(shí)例的個(gè)數(shù)，每個(gè)測(cè)試實(shí)例的第一行是一個(gè)整數(shù)N(1 <= N <= 100)，表示數(shù)塔的高度，接下來(lái)用N行數(shù)字表示數(shù)塔，其中第i行有個(gè)i個(gè)整數(shù)，且所有的整數(shù)均在區(qū)間[0,99]內(nèi)。

Output
對(duì)于每個(gè)測(cè)試實(shí)例，輸出可能得到的最大和，每個(gè)實(shí)例的輸出占一行。

Sample Input

1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output

30

解析

遞推公式：DP[i][j] = M[i][j] + max(DP[i+1][j], DP[i+1][j+1]) 自底向上計(jì)算到塔頂，得到的結(jié)果即為最大和

AC

#include<iostream> #include<algorithm> #include<cstring> using namespace std;int main() {int a[105][105];int t, n, i, j;while(cin>>t){while(t--){cin>>n;memset(a,0,sizeof(a));for(i=0; i<n; i++)for(j=0; j<=i; j++)cin>>a[i][j];for(i=n-2; i>=0; i--)for(j=0; j<=i; j++)a[i][j] = a[i][j] + max(a[i+1][j], a[i+1][j+1]);cout<<a[0][0]<<endl;}}return 0; }

7. 一只小蜜蜂

Problem Description
有一只經(jīng)過(guò)訓(xùn)練的蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行。請(qǐng)編程計(jì)算蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)。
其中，蜂房的結(jié)構(gòu)如下所示。

Input
輸入數(shù)據(jù)的第一行是一個(gè)整數(shù)N,表示測(cè)試實(shí)例的個(gè)數(shù)，然后是N 行數(shù)據(jù)，每行包含兩個(gè)整數(shù)a和b(0<a<b<50)。

Output
對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)，每個(gè)實(shí)例的輸出占一行。

Sample Input

2
1 2
3 6

Sample Output

1
3

解析

思路1：局部最優(yōu)解得到全局最優(yōu)解 蜂房5路線 = 蜂房3的路線 + 蜂房4的路線 蜂房6路線 = 蜂房4的路線 + 蜂房5的路線 。。。 蜂房n路線 = 蜂房n-2的路線 + 蜂房n-1的路線 斐波那契數(shù)列思路2：枚舉 1->2 (1種)：1->2; 1->3 (2種): 1->2->3; 1->3; 1->4 (3種): 1->2->4; 1->2->3->4; 1->3->4; 1->5 (5種): 1->2->3->5; 1->3->5; 1->2->4->5; 1->2->3->4->5; 1->3->4->5; 1->6 (8種): 1->4(3種)->6; 1->5(5種)->6; 得斐波那契數(shù)列唯一要注意的就是數(shù)比較大，得用long long類型

AC

#include <iostream> using namespace std;int main() {long long ans = 0, pre = 0;int T;cin>>T;while(T--){int a, b;cin>>a>>b;for (int i=2; i <= b-a+1; i++){if (i==2) {pre = 0;ans = 1;}else if (i==3) {pre = 1;ans = 2; continue;}else{ans = pre + ans;pre = ans - pre;}}cout << ans << endl;} return 0; }

8. 折線分割平面

Problem Description
我們看到過(guò)很多直線分割平面的題目，今天的這個(gè)題目稍微有些變化，我們要求的是n條折線分割平面的最大數(shù)目。比如，一條折線可以將平面分成兩部分，兩條折線最多可以將平面分成7部分，具體如下所示。

Input
輸入數(shù)據(jù)的第一行是一個(gè)整數(shù)C,表示測(cè)試實(shí)例的個(gè)數(shù)，然后是C 行數(shù)據(jù)，每行包含一個(gè)整數(shù)n(0<n<=10000),表示折線的數(shù)量。

Output
對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出平面的最大分割數(shù)，每個(gè)實(shí)例的輸出占一行。

Sample Input

2
1
2

Sample Output

2
7

解析

n條直線最多分平面問(wèn)題 題目大致如:n條直線，最多可以把平面分為多少個(gè)區(qū)域。 析:可能你以前就見過(guò)這題目，這充其量是一道初中的思考題。但一個(gè)類型的題目還是從簡(jiǎn)單的入手，才容易發(fā)現(xiàn)規(guī)律。 當(dāng)有n-1條直線時(shí)，平面最多被分成了f（n-1）個(gè)區(qū)域。 則第n條直線要是切成的區(qū)域數(shù)最多，就必須與每條直線相交且不能有同一交點(diǎn)。 這樣就會(huì)得到n-1個(gè)交點(diǎn)。 這些交點(diǎn)將第n條直線分為2條射線和n-2條線段。 而每條射線和線斷將已有的區(qū)域一分為二。這樣就多出了2+（n-2）個(gè)區(qū)域。 故：f(n)=f(n-1)+n =f(n-2)+(n-1)+n …… =f(1)+1+2+……+n =n(n+1)/2+1根據(jù)直線分平面可知，由交點(diǎn)決定了射線和線段的條數(shù)，進(jìn)而決定了新增的區(qū)域數(shù)。 當(dāng)n-1條折線時(shí)，區(qū)域數(shù)為f（n-1）。 為了使增加的區(qū)域最多，則折線的兩邊的線段要和n-1條折線的邊，即2*（n-1）條線段相交。 那么新增的線段數(shù)為4*（n-1），射線數(shù)為2。 但要注意的是，折線本身相鄰的兩線段只能增加一個(gè)區(qū)域。 故：f(n)=f(n-1)+4(n-1)+2-1 =f(n-1)+4(n-1)+1 =f(n-2)+4(n-2)+4(n-1)+2 …… =f(1)+4+4*2+……+4(n-1)+(n-1) =2n^2-n+1

AC

#include<iostream> using namespace std;int main() {int num,k;cin>>num;while(num--){cin>>k;cout<<2*k*k-k+1<<endl;}return 0; }

9. 獻(xiàn)給杭電五十周年校慶的禮物

Problem Description
今年是我們杭電建校五十周年，這是一個(gè)值得祝福的日子。我們?cè)撍徒o母校一個(gè)怎樣的禮物呢？對(duì)于目前的大家來(lái)說(shuō)，最好的禮物當(dāng)然是省賽中的好成績(jī)，我不能參賽，就送給學(xué)校一個(gè)DOOM III球形大蛋糕吧，這可是名牌，估計(jì)要花掉我半年的銀子呢。

想象著正式校慶那一天，校長(zhǎng)親自操刀，把這個(gè)大蛋糕分給各地趕來(lái)祝賀的校友們，大家一定很高興，呵呵，流口水了吧…

等一等，吃蛋糕之前先考大家一個(gè)問(wèn)題：如果校長(zhǎng)大人在蛋糕上切了N刀（校長(zhǎng)刀法極好，每一刀都是一個(gè)絕對(duì)的平面），最多可以把這個(gè)球形蛋糕切成幾塊呢？

做不出這個(gè)題目，沒(méi)有蛋糕吃的！
為-了-母-校-，為-了-蛋-糕-（不是為了DGMM，楓之羽最會(huì)浮想聯(lián)翩…），加-油-！

Input
輸入數(shù)據(jù)包含多個(gè)測(cè)試實(shí)例，每個(gè)實(shí)例占一行，每行包含一個(gè)整數(shù)n(1<=n<=1000)，表示切的刀數(shù)。

Output
對(duì)于每組輸入數(shù)據(jù)，請(qǐng)輸出對(duì)應(yīng)的蛋糕塊數(shù)，每個(gè)測(cè)試實(shí)例輸出一行。

Sample Input

1
2
3

Sample Output

2
4
8

解析

平面分割空間問(wèn)題 由二維的分割問(wèn)題可知，平面分割與線之間的交點(diǎn)有關(guān)，即交點(diǎn)決定射線和線段的條數(shù)，從而決定新增的區(qū)域數(shù)。 試想在三維中則是否與平面的交線有關(guān)呢？ 當(dāng)有n-1個(gè)平面時(shí)，分割的空間數(shù)為f(n-1)。 要有最多的空間數(shù)，則第n個(gè)平面需與前n-1個(gè)平面相交，且不能有共同的交線。即最多有n-1 條交線。 而這n-1條交線把第n個(gè)平面最多分割成g(n-1)個(gè)區(qū)域。 （g(n)為（1）中的直線分平面的個(gè)數(shù) ）此平面將原有的空間一分為二，則最多增加g(n-1)個(gè)空間。 故：f=f(n-1)+g(n-1) ps:g(n)=n(n+1)/2+1 =f(n-2)+g(n-2)+g(n-1) …… =f(1)+g(1)+g(2)+……+g(n-1) =2+(1*2+2*3+3*4+……+(n-1)n)/2+（n-1） =(1+2^2+3^2+4^2+……+n^2-1-2-3-……-n )/2+n+1 =(n^3+5n)/6+1

AC

#include <stdio.h>int main(){int n;while(scanf("%d", &n)!=EOF){printf("%d\n", (n*n*n+5*n)/6+1);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的入门-动态规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。