CUMTOJ算法实验二

算法 C++ 算法

发布时间 : 2019-10-12 00:38

阅读 :

问题 A: 最长公共子序列

题目描述

给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。
例如：Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列，Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y，请问它们的最长公共子序列的长度是多少？

输入

输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过100。

输出

对于每组输入，输出两个字符串的最长公共子序列的长度。

样例输入

abcfbc abfcab
programming contest
abcd mnp

样例输出

4
2
0

思路

用c[i][j]记录x序列前i个元素和y序列前j个元素的最长公共子序列长度。

确定初始状态的值：i == 0 || j == 0时，c[i][j] = 0。

状态转移方程：

if(x[i] == y[j]) c[i][j] = c[i-1][j-1]+1;
else c[i][j] = max(c[i-1][j],c[i][j-1]);
最后，c[lenx][leny]就是最长公共子序列的长度。

那么如何构造最优解呢？

新开一个二维数组，叫做b[i][j]：

（x[i] == y[j]）如果c[i][j]是由左上得到，则b[i][j] = 1
（x[i] != y[j]）如果c[i][j]是由上方得到，则b[i][j] = 2
（x[i] != y[j]）如果c[i][j]是由左方得到，则b[i][j] = 3
注：若x[i] != y[j]情况下左和上相等统一记为b[i][j] = 2

最后，由b数组倒推可得到最优解。

代码

#include <iostream>
#include <string.h>
using namespace std;
int main()
{
    const int max_num = 1000;
    int arr[max_num][max_num];
    int len_fir, len_sec;
    char fir_str[max_num], sec_str[max_num];
    while(cin >> fir_str >> sec_str)
    {
        len_fir = strlen(fir_str);
        len_sec = strlen(sec_str);
        memset(arr, 0, sizeof(arr));
        for(int i = 1; i <= len_fir; i++)
        {
            for(int j = 1; j <= len_sec; j++)
            {
                if(fir_str[i-1] == sec_str[j-1])
                    arr[i][j] = arr[i-1][j-1] + 1;
                else
                    arr[i][j] = max(arr[i-1][j], arr[i][j-1]);
            }
        }
        cout << arr[len_fir][len_sec] << endl;
    }
    return 0;
}

问题 B: 矩阵连乘

题目描述

给定n个矩阵{A1,A2,…,An}，及m个矩阵连乘的表达式，判断每个矩阵连乘表达式是否满足矩阵乘法法则，如果满足，则计算矩阵的最小连乘次数，如果不满足输出“MengMengDa“。

输入

输入数据由多组数据组成（不超过10组样例）。每组数据格式如下：
第一行是2个整数n (1≤n≤26)和m(1≤m≤3)，表示矩阵的个数。
接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数r和c，分别表示该矩阵的行数和列数，其中1 < r, c < 100。
第n+1行到第n+m行，每行是一个矩阵连乘的表达式(2 <= 矩阵个数 <= 100)。

输出

对于每个矩阵连乘表达式，如果运算不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“MengMengDa”，否则输出最小矩阵连乘次数。

数据保证结果不超过1e9。
对于每组数据，输出仅一行，即项目的IRR，四舍五入保留小数点后两位。

样例输入

3 2
A 10 100
B 5 50
C 100 5
ACB
ABC

样例输出

7500
MengMengDa

思路

先来回顾下我们上课学的矩阵连乘填表方法，我们把它封装成一个MatrixChain()函数。

回忆一下填表的过程，首先，因为如果只有一个矩阵的话，那就不需要乘了，结果肯定是0，对应地，我们把对角线全部置为0。for(int i = 1; i <= n; i++) dp[i][i] = 0;

然后写一个三层循环：

第一层循环r从2到n，代表连乘矩阵的个数
第二层循环i从1到n-r+1，代表左界下标
这时候右界下标j就等于i+r-1
第三层循环k从i到j-1，代表隔板位置，这个隔板把原来的问题一分为二

书上的代码把那个表对应的二维矩阵叫做m[i][j]，因为输入也叫m，所以我们就叫它dp[i][j]吧。

这样，让dp[i][j]中存储的是dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]的最小值。

先输入n个矩阵的名字（单个字符）、行数和列数。这时候我们可以使用一个数据结构——map，这种容器使用红黑树实现，插入、查找、删除的时间复杂度都是O(logn)。

注意：虽是单个字符，若让C++读入单个字符，可以为’\n，为了避免使用getchar()函数，通常使用元素个数为2的char数组存储单个字符。

m次query，每次读入一个字符串。令len = strlen(str)，若len个矩阵可连乘（对于每两个连续矩阵，前一个矩阵的列数=后一个矩阵的行数），则输出最小矩阵连乘次数，否则输出“MengMengDa”。

首先，不满足矩阵乘法法则的情况好判断，遍历一遍len个矩阵，若左矩阵列数与右矩阵的行数不同，则直接输出“MengMengDa”并break；
若满足矩阵连乘条件，则我们要构造p数组，构造过程参考代码；
可以封装一个void MatrixChain(int p[],int n)函数，用于执行dp，调用该函数后，结果就是dp[1][len]

代码

#include <iostream>
#include <string.h>
#include <map>
using namespace std;
const int max_num = 1005;
int dp[max_num][max_num];
struct Matrix {
    int r, c;
};
int main()
{
	void MatrixChain(int p[], int n);
    int n, m;
    while(cin >> n >> m)
    {
        map<char, Matrix> dir;
        char nam[8], str[105];
        int r, c;
        for(int i = 0; i < n; i++)
        {
            cin >> nam;
            cin >> r;
            cin >> c;
            Matrix tmp;
            tmp.r = r;
            tmp.c = c;
            dir[nam[0]] = tmp;
        }
        for(int cas = 0; cas < m; cas++)
        {
            cin >> str;
            int len = strlen(str);
            int p[max_num];
            p[0] = dir[str[0]].r;
            p[1] = dir[str[0]].c;
            bool flag = true;
            for(int i = 1; i < len; i++)
            {
                if(dir[str[i]].r != dir[str[i-1]].c)
                {
                    flag = false;
                    break;
                }
                p[i + 1] = dir[str[i]].c;
            }
            if(!flag)
				cout << "MengMengDa" << endl;
            else {
                MatrixChain(p, len);
                cout << dp[1][len] << endl;
            }
        }
    }
    return 0;
}
void MatrixChain(int p[], int n)
{
    for(int i = 1; i <= n; i++)
		dp[i][i] = 0;
    for(int r = 2; r <= n; r++)
    {
        for(int i = 1; i <= n - r + 1; i++)
        {
            int j = i + r - 1;
            dp[i][j] = dp[i + 1][j] + p[i-1] * p[i] * p[j];
            for(int k = i + 1; k < j; k++)
            {
                int t = dp[i][k] + dp[k + 1][j] + p[i-1] * p[k] * p[j];
                dp[i][j] = min(dp[i][j], t);
            }
        }
    }
}

问题 C: 01背包问题

题目描述

已知有N种物品和一个可容纳C重量的背包。每种物品i的重量为Wi，价值为Pi。那么，采用怎样的装包方法才会使装入背包物品的总价值最大。

输入

包含多组测试数据。第一行为一个整数T(1<=T<=10)，代表测试数据个数。

接下来有T组测试数据。每组测试数据第一行为背包的重量C(C<10000)和物品个数N(N<1000)。接下来的N行分别为物品的重量cost(1<=cost<=100)和价值val(1<=val<=3000000)。（注意：结果可能超过int范围）

输出

对每组测试数据，输出其对应的所装物品的最大价值。

样例输入

1
10 5
2 6
2 3
6 5
5 4
4 6

样例输出

15

思路

先看题目最后的注意，结果可能超过int范围，故采用long long类型。我一般这样写：typefef long long ll;把它“重命名”一下，以后写起来比较简便。

注意在stdio（scanf、printf）中，要写出%lld。

有两种写法（分别对应下面的代码1和代码2）.

第一种，也就是书上的这种，arr[i][j]代表从第i件物品开始的、在最大容量为j的情况下可以获得的最大收益，最后结果保存在arr[1][c]；

代码

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long ll;
const int max_num = 1005;
ll arr[max_num][max_num];
int main()
{
    int t, n;
    ll c, w[max_num], v[max_num];
    cin >> t;
    while(t--)
    {
        scanf("%lld %d", &c, &n);
        for(int i = 1; i <= n; i++)
            scanf("%lld %lld", &w[i], &v[i]);
        int i, j, jMax = min(w[n] - 1, c);
        for(j = 0; j <= jMax; j++)
			arr[n][j] = 0;
        for(j = w[n]; j <= c; j++)
			arr[n][j] = v[n];
        for(i = n - 1; i > 1; i--)
        {
            jMax = min(w[i] - 1, c);
            for(j = 0; j <= jMax; j++)
				arr[i][j] = arr[i + 1][j];
            for(j = w[i]; j <= c; j++)
				arr[i][j] = max(arr[i + 1][j] , arr[i + 1][j-w[i]] + v[i]);
        }
        arr[1][c] = arr[2][c];
        if(c >= w[1])
			arr[1][c] = max(arr[1][c], arr[2][c-w[1]] + v[1]);
        printf("%lld\n", arr[1][c]);
    }
    return 0;
}

问题 D: 最大子段和

题目描述

给定n个整数组成的序列a1,a2,…an, 求子段和ai+ai+1+…+aj（子段可为空集）的最大值。

输入

包含多组测试数据。第一行为一个整数T(1<=T<=20)，代表测试数据个数。

每组测试数据第一行为一个整数n，代表有n个整数(1<=n<=10000)。

接下来一行有n个数x(-1000<=x<=1000)。

输出

输出其对应的最大子段和。

样例输入

1
6
2 -11 4 13 -1 2

样例输出

18

思路

DP基础题，新开一个b辅助数组，我们这样定义它：auxiliary_arr[j]存储选取第j个元素时arr[1],…,arr[j]的最大子段和。

递归定义auxiliary_arr数组（b[0]需初始化为0）：

（前面为正数，有用则要）若auxiliary_arr[j-1] > 0，则

auxiliary_arr[j] = auxiliary_arr[j-1] + arr[j]；

（前面为负数，无用则丢）否则

auxiliary_arr[j] = arr[j]

则易得出最优值为b数组中的最大值（因为题目要求若为负数则输出0，所以要和0做一次max）。

代码

#include <iostream>
#include <stdio.h>
using namespace std;
const int max_num = 10000;
int main()
{
    int t, n, arr[max_num], auxiliary_arr[max_num]= { 0 };
    cin >> t;
    while(t--)
    {
        int result = 0;
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            cin >> arr[i];
            if(auxiliary_arr[i-1] > 0)
				auxiliary_arr[i] = auxiliary_arr[i - 1] + arr[i];
            else
				auxiliary_arr[i] = arr[i];
            result = max(result, auxiliary_arr[i]);
        }
        cout << result << endl;
    }
    return 0;
}

问题 E: 汽水瓶【25】

题目描述

有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶，最多可以换多少瓶汽水喝？

输入

输入文件最多包含10组测试数据，每个数据占一行，仅包含一个正整数n(1≤n≤100)，表示小张手上的空汽水瓶数。n=0表示输入结束，你的程序不应当处理这一行。

输出

对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出 0

样例输入

3
10
81
0

样例输出

1
5
40

思路

result 存储这一轮完成后的结果，emp 存储这一轮完成后的空瓶数。

题目怎么来，我们就怎么写代码。模拟一下，用 tmp 存储这一轮喝的汽水的瓶数，则有：

1 2	result += tmp; emp = emp % 3 + tmp;

循环的条件是什么？答案很显然是 while(emp >= 2)。

emp == 2 的时候怎么处理？答案是先借一瓶，即 emp++。

最终，输出 result 即可。

代码

#include <iostream>
using namespace std;
int main()
{
    int n;
    while((cin >> n) && n)
    {
        int result = 0, emp = n, tmp;
        while(emp >= 2)
        {
            if(emp == 2)
				emp++;
            tmp = emp / 3;
            result += tmp;
            emp = emp % 3 + tmp;
        }
        cout << result << endl;
    }
    return 0;
}

声明

本文参考了我矿学长的文章
https://comydream.github.io/2018/10/09/algorithm-experiment-2/

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 xingshuaikun@163.com。