1. AI技术聚合首页
  2. IT

东方 – 动态规划

心中带点小风骚 • • IT • 阅读 29

动态规划基础

1.dp基础

1649. 前缀最大值

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n,x,maxn;
	long long sum=0;
	cin>>n>>x;
	vector<int> a(n+1);
	a[1] = x;
	maxn = x;
	sum += x;
	for(int i=2; i<=n; i++)
	{
		a[i] = (379 * a[i-1] + 131) % 997;
		maxn = max(maxn,a[i]);
		sum += maxn;
	}
	cout<<sum<<endl;
	return 0;
}

函数版本

#include <iostream>
#include <vector>
using namespace std;

// 计算前缀最大值之和的函数
long long calculatePrefixMaxSum(int n, int x) {
    vector<int> sequence(n);
    sequence[0] = x;
    
    long long sum = x;
    int currentMax = x;

    for (int i = 1; i < n; ++i) {
        sequence[i] = (379 * sequence[i - 1] + 131) % 997;
        currentMax = max(currentMax, sequence[i]);
        sum += currentMax;
    }

    return sum;
}

int main() {
    int n, x;
    cin >> n >> x;

    cout << calculatePrefixMaxSum(n, x) << endl;

    return 0;
}

1650. 前缀最小值

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n,x,minn;
	long long sum=0;
	cin>>n>>x;
	vector<int> a(n+1);
	a[1] = x;
	minn = x;
	sum += x;
	for(int i=2; i<=n; i++)
	{
		a[i] = (379 * a[i-1] + 131) % 997;
		minn = min(minn,a[i]);
		sum += minn;
	}
	cout<<sum<<endl;
	return 0;
}

1651 – 跳格子

#include <iostream>
#include <limits.h>
#include <vector>

using namespace std;

int main()
{
	int n,A,B,C;
	cin>>n>>A>>B>>C;
	vector<int> x(n+1);
    for (int i = 1; i <= n; i++){
		int tmp = ((long long)A * i * i + B * i + C) % 20000;
		x[i] = tmp - 10000;
	}
	vector<int> dp(n+1,INT_MIN);
	dp[0] = 0;
	if(n>=1) dp[1] = x[1];
	
	for(int i=2; i<=n; i++)
	{
		dp[i] = max(dp[i - 1], i >= 2 ? dp[i - 2] : INT_MIN) + x[i];  // 计算每个格子的最大得分
	}
	int maxScore = max(dp[n], dp[n - 1]);  // 在最后一个格子和倒数第二个格子中选择最大得分
    cout << maxScore;  // 输出可能的最大得分
	return 0;
}

1652. 跳格子2

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int main() {
    int n, A, B, C;
    cin >> n >> A >> B >> C;

    vector<int> x(n + 1);
    for (int i = 1; i <= n; i++) {
        int tmp = ((long long)A * i * i + B * i + C) % 20000;
        x[i] = tmp - 10000;  // 生成每个格子的分数
    }

    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;  // 初始位置得分为0
    if (n >= 1) dp[1] = x[1];  // 第一个格子的得分

    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i - 1], i >= 2 ? dp[i - 2] : INT_MAX) + x[i];  // 计算每个格子的最小得分
    }

    int minScore = min(dp[n], dp[n - 1]);  // 在最后一个格子和倒数第二个格子中选择最小得分
    cout << minScore;  // 输出可能的最小得分
    return 0;
}

1589 – 最大部分和（连续部分和）

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n;
	cin>>n;
	vector <int> v(n+1),dp(n+1);
	for(int i=1; i<=n; i++)
	{
		cin>>v[i];
	}
	dp[1] = v[1];
	int maxn = v[1];
	for(int i=2; i<=n; i++)
	{
		dp[i] = max(v[i],dp[i-1]+v[i]);
		maxn = max(dp[i],maxn);
	}
	cout<<maxn;
	return 0;
}

1653. 取数

状态定义：定义 dp[i] 为在前 i 个数中，按题目要求取数能得到的最大和。
状态转移：
如果选择第 i 个数，那么不能选择第 i-1 个数，所以最大和是 dp[i-2] + arr[i]。
如果不选择第 i 个数，那么最大和是 dp[i-1]。
dp[i] 是上述两者中的最大值。
初始条件：
dp[0] 应该为 0，因为没有数可选。
dp[1] 应该为第一个数的值。
目标：找出 dp[n] 的值。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> arr(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    vector<int> dp(N + 1, 0);
    dp[1] = arr[1];

    for (int i = 2; i <= N; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + arr[i]);
    }

    cout << dp[N];
    return 0;
}

1794 – 最长不下降子序列（LIS）

为了解决这个问题，我们可以使用动态规划的方法来求解最长不下降子序列（LIS，Longest Increasing Subsequence）。动态规划是一种将复杂问题分解成更小子问题的方法，通过解决子问题并将结果存储起来以避免重复计算，达到优化整体解决方案的效率。

解决LIS问题的基本思路是创建一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长不下降子序列的长度。对于每个元素 a[i]，我们需要找到所有 j < i 且 a[j] ≤ a[i] 的元素，并在所有可能的子序列中选择最长的一个，然后加上 a[i] 本身。

以下是具体的步骤：

  1. 初始化一个长度为 n 的数组 dp，每个元素设为 1，因为每个元素本身至少可以构成长度为 1 的子序列。
  2. 双层循环遍历数组。对于每个 i（从第二个元素开始），遍历所有在 i 之前的元素 j。如果 a[j] ≤ a[i]，则更新 dp[i] 为 max(dp[i], dp[j] + 1)。
  3. 在所有的 dp[i] 中找出最大值，这就是最长不下降子序列的长度。

下面是这个思路的C++实现，并附有注释：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // 初始化dp数组，每个元素初始长度为1
    int max_length = 1;   // 初始化最长长度为1

    // 构建dp数组
    for (int i = 1; i < n; i++) { // 从第二个元素开始
        for (int j = 0; j < i; j++) { // 检查所有前面的元素
            if (nums[j] <= nums[i]) { // 如果前面的元素小于等于当前元素
                dp[i] = max(dp[i], dp[j] + 1); // 更新dp[i]
            }
        }
        max_length = max(max_length, dp[i]); // 更新最长长度
    }

    return max_length; // 返回最长不下降子序列的长度
}

int main() {
    int n;
    cin >> n; // 读取元素数量

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i]; // 读取每个元素
    }

    cout << longestIncreasingSubsequence(nums) << endl; // 输出最长不下降子序列的长度

    return 0;
}

解答二：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // 初始化dp数组，每个元素初始长度为1

    // 构建dp数组
    for (int i = 1; i < n; i++) { // 从第二个元素开始
        for (int j = 0; j < i; j++) { // 检查所有前面的元素
            if (nums[j] <= nums[i]) { // 如果前面的元素小于等于当前元素
                dp[i] = max(dp[i], dp[j] + 1); // 更新dp[i]
            }
        }
    }

    // 在dp数组中找到最大值
    return *max_element(dp.begin(), dp.end());
}

int main() {
    int n;
    cin >> n; // 读取元素数量

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i]; // 读取每个元素
    }

    cout << longestIncreasingSubsequence(nums) << endl; // 输出最长不下降子序列的长度

    return 0;
}

这段代码首先读取元素个数 n，然后读取 n 个整数到向量 nums 中。longestIncreasingSubsequence 函数用来计算并返回最长不下降子序列的长度。最后，这个长度被输出到控制台。

例如，对于输入样例：

10
3 18 7 14 10 12 23 41 16 24

这段代码将会输出最长不下降子序列的长度，例如可能是 6（对应于子序列 3 7 10 12 16 24）。

*max_element(dp.begin(), dp.end()) 这个表达式在 C++ 中涉及到几个重要的概念和库函数。下面是详细的解释：

  1. 标准模板库（STL）：max_element 函数是 C++ 标准模板库（STL）中的一部分。STL 提供了一套通用的模板类和函数，这大大简化了数据结构和算法的实现。

  2. max_element 函数：这是 <algorithm> 头文件中的一个函数，用于在指定范围内找到最大元素的迭代器。max_element 接受两个参数，分别是要搜索的范围的开始和结束迭代器。

    • dp.begin() 返回一个迭代器，指向 dp 容器的第一个元素。
    • dp.end() 返回一个迭代器，指向 dp 容器的末尾（注：这不是最后一个元素，而是最后一个元素之后的位置）。

    max_element 函数遍历这个范围，并返回一个迭代器，指向找到的最大元素。

  3. 解引用运算符（*）：max_element 返回的是一个迭代器，而不是实际的元素值。为了获取迭代器指向的元素的值，需要使用解引用运算符（*）。所以 *max_element(dp.begin(), dp.end()) 实际上获取的是 dp 容器中最大元素的值。

  4. 向量容器（vector）：dp 是一个 vector<int> 类型的对象。向量（vector）是 STL 中的一种序列容器，可以动态地存储元素，大小可以根据需要自动调整。

综上所述，*max_element(dp.begin(), dp.end()) 这个表达式的作用是在 dp 容器中找出最大的元素，并返回它的值。这是实现动态规划算法时常见的一种方法，用于在存储中间结果的容器中找到所需的最终结果。 这个表达式在 C++ 中涉及到几个重要的概念和库函数。下面是详细的解释：

  1. 标准模板库（STL）：max_element 函数是 C++ 标准模板库（STL）中的一部分。STL 提供了一套通用的模板类和函数，这大大简化了数据结构和算法的实现。

  2. max_element 函数：这是 <algorithm> 头文件中的一个函数，用于在指定范围内找到最大元素的迭代器。max_element 接受两个参数，分别是要搜索的范围的开始和结束迭代器。

    • dp.begin() 返回一个迭代器，指向 dp 容器的第一个元素。
    • dp.end() 返回一个迭代器，指向 dp 容器的末尾（注：这不是最后一个元素，而是最后一个元素之后的位置）。

    max_element 函数遍历这个范围，并返回一个迭代器，指向找到的最大元素。

  3. 解引用运算符（*）：max_element 返回的是一个迭代器，而不是实际的元素值。为了获取迭代器指向的元素的值，需要使用解引用运算符（*）。所以 *max_element(dp.begin(), dp.end()) 实际上获取的是 dp 容器中最大元素的值。

  4. 向量容器（vector）：dp 是一个 vector<int> 类型的对象。向量（vector）是 STL 中的一种序列容器，可以动态地存储元素，大小可以根据需要自动调整。

综上所述，*max_element(dp.begin(), dp.end()) 这个表达式的作用是在 dp 容器中找出最大的元素，并返回它的值。这是实现动态规划算法时常见的一种方法，用于在存储中间结果的容器中找到所需的最终结果。

1649 – 前缀最大值

为了解决这个问题，我们可以使用一种简单有效的方法，即遍历数组的同时维护一个当前的最大值。我们不需要使用动态规划，因为动态规划通常用于解决有重叠子问题和最优子结构的问题，而这个问题没有重叠子问题。

解题思路如下：

  1. 生成数列：根据给定的公式和初始值（随机种子）生成数列。
  2. 遍历数列：初始化一个变量来存储当前的最大值，然后遍历数列。
  3. 对于每个元素，更新当前最大值（如果当前元素比当前最大值大，则将其设置为新的最大值）。
  4. 将当前最大值累加到总和中。
  5. 遍历完成后，输出总和。

这个方法的时间复杂度是 O(n)，其中 n 是数列的长度。下面是C++代码的实现，附有注释：

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x; // 读取数列的长度和随机种子

    long long sum = 0; // 用于存储前缀最大值之和
    int max_val = x; // 初始化最大值为随机种子

    // 生成数列并计算前缀最大值之和
    for (int i = 1; i <= n; i++) {
        if (i != 1) {
            x = (379 * x + 131) % 997; // 生成数列的下一个数
        }
        max_val = max(max_val, x); // 更新当前的最大值
        sum += max_val; // 将当前最大值加到总和中
    }

    cout << sum << endl; // 输出前缀最大值之和

    return 0;
}

这段代码首先读取数列的长度 n 和初始值 x。然后，它使用一个循环来生成数列的每个元素，并在每一步中更新当前的最大值和总和。循环结束后，它输出计算得到的前缀最大值之和。例如，对于输入样例 5 666，这段代码会输出 3408。

1277. 合唱队形求解

要解决这个问题，我们可以采用动态规划的方法。这个问题实际上是寻找最长的“双向递增子序列”。首先我们从左到右寻找以每个同学为顶点的最长递增子序列，然后从右到左寻找最长递减子序列。合唱队形实际上是这两个子序列的重叠部分，我们需要找到重叠最多的地方，这样出列的同学数就最少。

动态规划思路：

  1. 从左到右的最长递增子序列（LIS）：对于每个同学 i，找到以他为顶点，左边的最长递增子序列的长度。
  2. 从右到左的最长递减子序列（LDS）：对于每个同学 i，找到以他为顶点，右边的最长递减子序列的长度。
  3. 结合两个子序列：对于每个同学 i，合唱队形的长度为LIS[i] + LDS[i] – 1（减1是因为顶点同学被计算了两次）。
  4. 求解最少出列的同学数：总数 N 减去最长的合唱队形长度。

C++ 实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> height(N), lis(N, 1), lds(N, 1);
    for (int i = 0; i < N; ++i) {
        cin >> height[i];
    }

    // 计算LIS
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (height[j] < height[i]) {
                lis[i] = max(lis[i], lis[j] + 1);
            }
        }
    }

    // 计算LDS
    for (int i = N - 1; i >= 0; --i) {
        for (int j = N - 1; j > i; --j) {
            if (height[j] < height[i]) {
                lds[i] = max(lds[i], lds[j] + 1);
            }
        }
    }

    // 计算合唱队形的最大长度
    int maxChoir = 0;
    for (int i = 0; i < N; ++i) {
        maxChoir = max(maxChoir, lis[i] + lds[i] - 1);
    }

    cout << N - maxChoir; // 输出最少需要出列的同学数
    return 0;
}

这个程序首先读取同学的数量和他们的身高，然后分别计算每个同学为顶点时的LIS和LDS。接着，它找出最大的合唱队形长度，并计算出最少需要几位同学出列。

4.LIS和LCS

1893. 最长上升子序列LIS（2）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) tails.push_back(num);
        else *it = num;
    }
    return tails.size();
}

int main() {
    int N;
    cin >> N;
    vector<int> nums(N);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    cout << lengthOfLIS(nums) << endl;
    return 0;
}

1821. 最长公共子序列(LCS)(1)

如果不进行映射，直接使用动态规划求解两个序列的最长公共子序列（LCS）问题，你可以按照以下步骤进行：

直接解决LCS问题的动态规划方法

  1. 初始化：创建一个 (n+1) x (n+1) 的二维数组 dp，其中 dp[i][j] 表示 P1 的前 i 个元素和 P2 的前 j 个元素的最长公共子序列的长度。所有元素初始化为 0。

  2. 填充 dp 数组：遍历两个序列，对于每一对元素 P1[i] 和 P2[j]：

    • 如果 P1[i] == P2[j]，这意味着这两个元素可以成为最长公共子序列的一部分，所以 dp[i][j] = dp[i-1][j-1] + 1。
    • 如果 P1[i] != P2[j]，则最长公共子序列不包括这两个元素中的任何一个，因此 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，即考虑不包括当前元素 P1[i] 或 P2[j] 的情况下的最长公共子序列的长度。

  3. 遍历完成后，dp[n][n] 存储的就是两个序列的最长公共子序列的长度。

示例代码

以下是不进行映射直接求解LCS的C++代码示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> p1(n), p2(n);
    for (int i = 0; i < n; ++i) {
        cin >> p1[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> p2[i];
    }

    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p1[i-1] == p2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    cout << dp[n][n] << endl;
    return 0;
}

这段代码直接计算了两个序列的最长公共子序列的长度，不需要将一个序列映射到另一个序列的索引上。这种方法是标准的动态规划解法，适用于任意两个序列的最长公共子序列问题，不仅限于排列。

1822 – 最长公共子序列(LCS)(2)

要解决这个问题，我们可以使用动态规划的思想，但是直接应用传统的最长公共子序列(LCS)算法对于这个问题的数据规模（(n \leq 100000)）来说是不切实际的，因为那需要(O(n^2))的时间复杂度，这在(n)很大时是不可接受的。

解题思路

  1. 转换问题为最长上升子序列 (LIS): 首先，我们注意到两个排列都是(1)到(n)的全排列，所以我们可以将其中一个排列用作索引，将另一个排列映射成一个新的序列，这样问题就转化为了寻找这个新序列的最长上升子序列（LIS）。

  2. 计算LIS: 使用动态规划计算LIS的时间复杂度是(O(n^2))，但是有一个更高效的(O(n \log n))算法。

实现步骤

  1. 将第一个排列的元素值作为索引，位置作为值，构造一个映射数组，例如排列[3, 1, 2]可以转化为映射[2, 3, 1]，意味着数字1在位置2，数字2在位置3，数字3在位置1。

  2. 使用第二个排列，根据第一步中构建的映射，转换为一个新的序列，这个新序列中的元素顺序代表了第二个排列中的元素在第一个排列中的相对位置。

  3. 在转换后的序列上应用(O(n \log n))的LIS算法，找到最长上升子序列的长度。

C++代码示例
下面是一个实现的简化版本：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 函数用于计算最长上升子序列的长度
int LIS(vector<int>& nums) {
    vector<int> dp;
    for (int x : nums) {
        auto it = lower_bound(dp.begin(), dp.end(), x);
        if (it == dp.end()) dp.push_back(x);
        else *it = x;
    }
    return dp.size();
}

int main() {
    int n;
    cin >> n;
    vector<int> p1(n), p2(n), map(n+1);
    for (int i = 0; i < n; ++i) {
        cin >> p1[i];
        map[p1[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        cin >> p2[i];
        p2[i] = map[p2[i]]; // 转换为新序列，反映p2在p1中的相对位置
    }
    cout << LIS(p2) << endl; // 计算并输出最长上升子序列的长度
    return 0;
}

这段代码首先读取两个排列，然后通过映射和转换将问题转化为一个最长上升子序列问题，并利用(O(n \log n))复杂度的算法求解。这样，我们就可以在可接受的时间内处理规模达到(100000)的数据。

版权声明：本文为博主作者：天秀信息学奥赛原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/m0_46192147/article/details/135961685

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
心中带点小风骚的头像心中带点小风骚普通用户
0
上一篇 2024年4月1日
下一篇 2024年4月1日

相关推荐