算法设计与分析_练习三_动态规划算法

目录

01:最长单调递增子序列

02:点菜

03:合唱队形

04:数塔问题

05:最大子段和

06:最长公共子序列

---

01:最长单调递增子序列

描述

一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入

输入两行.第一行输入n（n<=1000）的值，第二行输入n各数

输出

最大上升子序列的长度

样例输入

8
65 158 170 155 239 300 207 389

样例输出

6

#include 
using namespace std;
 
#define NUM 100
int a[NUM]; //序列L
int LIS(int n) {
    int b[NUM] = {0}; //辅助数组b
    int i, j;
    b[1] = 1;	//以a[1]结尾的子序列中只包含一个元素
    int max = 0; //数组b的最大值
    for (i = 2; i <= n; i++) {
        int k = 0;
        for (j = 1; j < i; j++) { //0~i-1之间，b的最大值
            if (a[j] <= a[i] && k < b[j]) k = b[j];
        }
        b[i] = k + 1;
        if (max < b[i]) {
            max = b[i];
        }
    }
    return max;
}
 
int main() {
    int n, i;
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cout << LIS(n);
    return 0;
}

 

02:点菜

描述

题目描述：umi拿到了uoi的镭牌后，立刻拉着基友小A到了一家餐馆，很低端的那种。uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。不过uim由于买了一些书，口袋里只剩M元(M≤10000)。餐馆虽低端，但是菜品种类不少，有N种(N≤100)，第i种卖ai元(ai ≤1000)。由于是很低端的餐馆，所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”，所以他点单一定刚好把uim身上所有钱花完。他想知道有多少种点菜方法。

输入

第一行是两个数字，表示N和M。

第二行起N个正数ai（可以有相同的数字，每个数字均在10001000以内）。

输出

一个正整数，表示点菜方案数，保证答案的范围在int之内。

样例输入

4 4
1 1 2 2

样例输出

3

#include 
using namespace std;
 
int f[101][1001], v[101]; //f[][]为方法数
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i]; // 输入每种菜的价格
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            //j元买不了这个菜，不买，则前i种菜花费j元的方法=前i-1种菜j花费j元的方法
            if (j < v[i])   f[i][j] = f[i - 1][j];
            //j元刚好买这个菜，则前i种菜花费j元的方法=前i-1种菜花费j元的方法加上只买这一个菜的方法(1种)
            if (j == v[i])  f[i][j] = f[i - 1][j] + 1;
            //j元买这个菜还有剩余，则f[i][j]为前i-1种菜花费j元的方法加上前i-1种菜花费j-v[i](因为还要买这个菜)的方法
            if (j > v[i])   f[i][j] = f[i - 1][j] + f[i - 1][j - v[i]];
        }
    }
    cout << f[n][m];
    return 0;
}

 

03:合唱队形

描述

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，  则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入

输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。 第二有N个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出

输出最少需要几位同学出列。

样例输入

8
186 186 150 200 160 130 197 220

样例输出

4

#include 
using namespace std;
 
int n, a[110], f[110][2], MAX; //f[i][1]表示上升子序列的个数，f[i][2]表示下降子序列的个数
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        int mx = 0;
        for(int j = 1; j < i; j++) {
            if(a[j] < a[i]) {
                mx = max(mx, f[j][1]); //求上升子序列的最大值，也就是第一部分可以留下的最大人数
            }
        }
        f[i][1] = mx + 1;
    }
    for(int i = n; i >= 1; i--) {
        int mx = 0;
        for(int j = n; j > i; j--) {
            if(a[j] < a[i]) {
                mx = max(mx, f[j][2]);  //求下降子序列的最大值，也就是第二部分可以留下的最大人数
            }
        }
        f[i][2] = mx + 1;
         //f[i][1]+f[i][2]-1表示当a[i]最高点时留下的人数，这里减一，因为上升和下降的个数都包括了最高点，所以减去一个
        MAX = max(MAX, f[i][1] + f[i][2] - 1);
    }
    cout << n - MAX << endl;
    return 0;
}

 

04:数塔问题

描述

设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示：

若要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。

输入

第一行为n(n<50)，表示数塔的层数
从第2行至n+1行，每行有若干个数据，表示数塔中的数值。

输出

最大的路径值。

样例输入

5
13
11  8
12  7  26
6  14  15  8
12  7  13  24  11

样例输出

86

#include 
using namespace std;
 
#define NUM 100
int tri[NUM][NUM];
int triangle(int n) {
    int i, j;
    for (i = n - 2; i >= 0; i--) {
        for (j = 0; j <= i; j++) {
            if( tri[i + 1][j] > tri[i + 1][j + 1]) {
                tri[i][j] = tri[i][j] + tri[i + 1][j]; //向左走
            } else {
                tri[i][j] = tri[i][j] + tri[i + 1][j + 1]; //向右走
            }
        }
    }
    return  tri[0][0];
}
 
int main() {
    int n, i, j;
    cin >> n;
    for(i = 0; i < n; i++) {
        for(j = 0; j <= i; j++) {
            cin >> tri[i][j];
        }
    }
    cout << triangle(n);
}

 

05:最大子段和

描述

问题： 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-20,11,-4,13,-5,-2)时，最大子段和为20。

输入

输入n及n个数

输出

子段和的最大值

样例输入

6
-20 11 -4 13 -5 -2

样例输出

20

#include 
using namespace std;
 
#define NUM 1001
int a[NUM];
int MaxSum(int n, int &besti, int &bestj) {
    int sum = 0;
    int b = 0;
    // 当b[i-1]<=0时,记录b[i]=a[i]的位置
    int begin = 0;
    for(int i = 1; i <= n; i++) {
        if(b > 0) b += a[i];
        else {
            b = a[i];    // 更新到最新的位置
            begin = i;
        }
        if(b > sum) {
            sum = b;
            // 得到新的最优值时,更新左右边界
            besti = begin;
            bestj = i;
        }
    }
    return sum;
}
 
int main() {
    int n, besti, bestj, i;
    besti = 0;
    bestj = 0;
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cout << MaxSum(n, besti, bestj);
    return 0;
}

 

06:最长公共子序列

描述

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列。

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

输入

三行.第一行m和n,分别表示两个子序列的长度（符号的个数）
接下来两行，分别表示X和Y

输出

最长公共子序列的长度

样例输入

7 6
ABCBDAB
BDCABA

样例输出

4

#include 
using namespace std;
 
#define NUM 100
int c[NUM][NUM]; // LCS长度的计算,x[1~i]和y[1~j]之间的公共子序列的长度
// int b[NUM][NUM]; // LCS字符的搜索过程,辅助完成最优解的计算
void LCSLength(int m, int n, const char x[], char y[]) {
    int i, j;
    // 数组c的第0行、第0列置0
    for(i = 1; i <= m; i++) c[i][0] = 0;
    for(i = 1; i <= 0; i++) c[0][i] = 0;
    //根据递推公式构造数组c
    for(i = 1; i <= m; i++) {
        for(j = 1; j <= n; j++) {
            if(x[i] == y[j]) {      //↖
                c[i][j] = c[i - 1][j - 1] + 1;
                // b[i][j] = 1;
            } else if(c[i - 1][j] > c[i][j - 1]) { //↑
                c[i][j] = c[i - 1][j];
                // b[i][j] = 2;
            } else { //←
                c[i][j] = c[i][j - 1];
                // b[i][j] = 3;
            }
        }
    }
}
 
//void LCS(int i, int j, char x[]) {
//    if(i == 0 || j == 0)return;
//    if(b[i][j] == 1) {
//        LCS(i - 1, j - 1, x);
//        cout << x[i] << " ";
//    } else if(b[i][j] == 2) LCS(i - 1, j, x);
//    else LCS(i, j - 1, x);
//}
 
int main() {
    char x[NUM];
    char y[NUM];
    int  m, n, i;
    cin >> m >> n;
    for(i = 1; i <= m; i++) {
        cin >> x[i];
    }
    for(i = 1; i <= n; i++) {
        cin >> y[i];
    }
    LCSLength(m, n, x, y);
    cout << c[m][n]; // 输出子序列长度
//    LCS(m, n, x);
    return 0;
}