HDU1159——通用子序列,HDU1160——FatMouse的速度、HDU1165——艾迪的研究 II

2024-08-22 21:44

本文主要是介绍HDU1159——通用子序列,HDU1160——FatMouse的速度、HDU1165——艾迪的研究 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

HDU1159——通用子序列

题目描述

问题 - 1159 (hdu.edu.cn)

问题描述
给定序列的子序列是给定的序列,其中遗漏了一些元素(可能没有)。给定一个序列 X = <x1, x2, ..., xm>如果存在一个严格递增的 X 索引序列 <i1, i2, ..., ik>>,则另一个序列 Z = <z1, z2, ..., zk 是 X 的子序列,使得所有 j = 1,2,...,k, xij = zj。例如,Z = <a, b, f, c> 是 X = <a, b, c, f, b, c> 的子序列,索引序列为 <1, 2, 4, 6>。给定两个序列 X 和 Y,问题是找到 X 和 Y 的最大长度公共子序列的长度。
程序输入来自文本文件。文件中的每个数据集都包含两个字符串,分别表示给定的序列。序列之间由任意数量的空格分隔。输入数据正确无误。对于每组数据,程序都会在标准输出上打印从单独行的开头开始的最大长度公共子序列的长度。
 
样本输入
abcfbc abfcab
programming contest
abcd mnp
 
示例输出
4
2
0

运行代码

//https://acm.hdu.edu.cn/showproblem.php?pid=1159
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int longest(const string& str1, const string& str2) {int m = str1.length();int n = str2.length();vector<vector<int>> dp(m + 1,vector<int>(n + 1, 0));for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (str1[i - 1] == str2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];
}int main() {string str1, str2;while (cin >> str1 >> str2) {cout << longest(str1, str2) << endl;}return 0;
}

代码思路

使用动态规划的思想来求解两个字符串的最长公共子序列(Longest Common Subsequence,LCS)的长度。动态规划是一种通过把原问题分解为相对简单的子问题,并保存子问题的解来避免重复计算,从而解决复杂问题的方法。

  1. 参数设置:该函数接收两个字符串str1str2作为参数,代表要计算最长公共子序列的两个序列。

  2. 初始化动态规划数组:首先获取两个字符串的长度,分别存储在变量mn中。创建一个二维向量dp,大小为(m + 1) x (n + 1),并初始化为全零。这里的dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列的长度。

  3. 动态规划过程:使用两个嵌套的循环遍历两个字符串的所有可能子序列组合。如果str1[i - 1](即str1的第i个字符)和str2[j - 1](即str2的第j个字符)相等,说明找到了一个公共字符,此时dp[i][j]的值应该是dp[i - 1][j - 1] + 1,也就是两个字符串都去掉当前这个公共字符后的最长公共子序列长度加一。如果两个字符不相等,那么dp[i][j]的值应该是dp[i - 1][j]dp[i][j - 1]中的较大值。这是因为如果当前字符不相等,最长公共子序列要么来自于不考虑str1的当前字符(即dp[i - 1][j]),要么来自于不考虑str2的当前字符(即dp[i][j - 1])。

  4. 返回结果:最终,dp[m][n]就存储了str1str2的最长公共子序列的长度,函数返回这个值。

HDU1160——FatMouse的速度

题目描述

问题 - 1160 (hdu.edu.cn)

问题描述
FatMouse认为,老鼠越胖,它跑得越快。为了反驳这一点,你想要获取一组老鼠的数据,并将这些数据的尽可能大的子集放入一个序列中,以便权重增加,但速度下降。
输入
输入包含一堆鼠标的数据,每行一只鼠标,在文件末尾终止。特定鼠标的数据将由一对整数组成:第一个表示其大小(以克为单位),第二个表示其速度(以厘米/秒为单位)。两个整数都在 1 到 10000 之间。每个测试用例中的数据将包含最多 1000 只小鼠的信息。两只老鼠可能具有相同的重量、相同的速度,甚至相同的重量和速度。
输出
您的程序应输出一系列数据行;第一行应包含数字 n;剩下的 N 行都应包含一个正整数(每个行代表一只老鼠)。如果这 n 个整数是 m[1]、m[2],..., m[n],那么一定是W[m[1]] < W[m[2]] < ...< W[m[n]]和S[m[1]] > S[m[2]] > ...> S[m[n]]为了使答案正确,n 应尽可能大。所有的不平等都是严格的:重量必须严格增加,速度必须严格减少。对于给定的输入,可能有许多正确的输出,您的程序只需要找到一个。
 

运行代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>struct Node {int w, v, num;Node(int w, int v, int num) : w(w), v(v), num(num) {}
};bool compare(const Node& a, const Node& b) {return a.w < b.w || (a.w == b.w && a.v > b.v);
}int main() {std::vector<Node> nodes;int w, v;while (std::cin >> w >> v) {nodes.emplace_back(w, v, nodes.size() + 1);}std::sort(nodes.begin(), nodes.end(), compare);int n = nodes.size();std::vector<int> dp(n, 1);std::vector<int> pre(n, -1);int maxLen = 0, endIndex = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nodes[j].w < nodes[i].w && nodes[j].v > nodes[i].v && dp[i] < dp[j] + 1) {dp[i] = dp[j] + 1;pre[i] = j;}}if (dp[i] > maxLen) {maxLen = dp[i];endIndex = i;}}std::cout << maxLen << std::endl;std::stack<int> st;while (endIndex!= -1) {st.push(endIndex);endIndex = pre[endIndex];}while (!st.empty()) {std::cout << nodes[st.top()].num << std::endl;st.pop();}return 0;
}

代码思路

  1. 输入与存储:使用 while (std::cin >> w >> v) 循环不断读取输入的重量和价值数据,将其创建为 Node 结构体对象,并存储在 std::vector<Node> nodes 中。每个 Node 结构体包含重量 w、价值 v 和编号 num

  2. 排序:对 nodes 容器中的物品按照重量 w 升序排列,如果重量相等,则按照价值 v 降序排列。这样的排序是为了方便后续在遍历物品时,只需要考虑前面的物品是否满足条件即可,因为后面物品的重量一定大于等于前面的物品重量。

  3. 动态规划求解最长子序列:创建两个长度为 nn 为物品数量)的辅助数组 dp 和 pre。其中 dp[i] 表示以第 i 个物品结尾的最长子序列长度,pre[i] 表示最长子序列中第 i 个物品的前一个物品在 nodes 中的索引。两层循环遍历物品:

    • 内层循环遍历 i 之前的物品 j,如果物品 j 的重量小于物品 i 的重量且物品 j 的价值大于物品 i 的价值,说明物品 j 可以作为物品 i 的前驱物品。如果此时以物品 i 结尾的子序列长度小于以物品 j 结尾的子序列长度加一,就更新 dp[i] 和 pre[i]
    • 外层循环遍历每个物品 i
    • 在遍历过程中,记录最长子序列的长度 maxLen 和最长子序列最后一个物品的索引 endIndex
  4. 输出结果:首先输出最长子序列的长度 maxLen。然后使用栈 std::stack<int> st 来逆序输出最长子序列中物品的编号。从最长子序列的最后一个物品索引 endIndex 开始,不断根据 pre 数组找到前一个物品的索引,将索引压入栈中。最后依次弹出栈中的索引,根据索引在 nodes 中找到对应的物品编号并输出。

HDU1165——艾迪的研究 II

题目描述

问题 - 1165 (hdu.edu.cn)

运行代码

#include <iostream>const int M = 1000005;
int dp[4][M];void init() {for (int i = 0; i < M; ++i) {dp[0][i] = i + 1;dp[1][i] = i + 2;dp[2][i] = 2 * i + 3;}dp[3][0] = 5;for (int i = 1; i <= 24; ++i) dp[3][i] = 2 * dp[3][i - 1] + 3;
}int main() {init();int m, n;while (std::cin >> m >> n) {std::cout << dp[m][n] << '\n';}return 0;
}

代码思路

  1. 定义常量和数组

    • 定义常量 M 为 1000005,用于表示数组的大小上限。
    • 定义二维数组 dp[4][M],用于存储阿克曼函数在不同参数下的计算结果。
  2. 初始化函数 init():使用循环初始化 dp 数组:

    • 当 m = 2 时,dp[2][i] = 2 * i + 3,即 A(2, n) = 2 * n + 3
    • 当 m = 1 时,dp[1][i] = i + 2,即 A(1, n) = n + 2
    • 当 m = 0 时,dp[0][i] = i + 1,即 A(0, n) = n + 1
    • 对于 m = 3 的情况单独处理,先设置 dp[3][0] = 5,然后通过循环计算 dp[3][i] = 2 * dp[3][i - 1] + 3,即 A(3, n) 的值是根据前一个 n 的值递推得到的,并且限制 n 的范围在 24 以内。
  3. 主函数 main()

    • 调用 init() 函数进行初始化操作。
    • 使用 while (std::cin >> m >> n) 循环不断读取输入的 m 和 n 的值。
    • 对于每一组输入的 m 和 n,直接输出 dp[m][n],即阿克曼函数 A(m, n) 的值。

这篇关于HDU1159——通用子序列,HDU1160——FatMouse的速度、HDU1165——艾迪的研究 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1097482

相关文章

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

一种改进的red5集群方案的应用、基于Red5服务器集群负载均衡调度算法研究

转自: 一种改进的red5集群方案的应用: http://wenku.baidu.com/link?url=jYQ1wNwHVBqJ-5XCYq0PRligp6Y5q6BYXyISUsF56My8DP8dc9CZ4pZvpPz1abxJn8fojMrL0IyfmMHStpvkotqC1RWlRMGnzVL1X4IPOa_  基于Red5服务器集群负载均衡调度算法研究 http://ww

生信圆桌x生信分析平台:助力生物信息学研究的综合工具

介绍 少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 生物信息学的迅速发展催生了众多生信分析平台,这些平台通过集成各种生物信息学工具和算法,极大地简化了数据处理和分析流程,使研究人员能够更高效地从海量生物数据中提取有价值的信息。这些平台通常具备友好的用户界面和强大的计算能力,支持不同类型的生物数据分析,如基因组、转录组、蛋白质组等。

开题报告中的研究方法设计:AI能帮你做什么?

AIPaperGPT,论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗?研究方法部分是不是已经让你头疼到抓狂? 别急,这可是大多数人都会遇到的难题!尤其是研究方法设计这一块,选定性还是定量,怎么搞才能符合老师的要求? 每次到这儿,头脑一片空白。 好消息是,现在AI工具火得一塌糊涂,比如ChatGPT,居然能帮你在研究方法这块儿上出点主意。是不

研究人员在RSA大会上演示利用恶意JPEG图片入侵企业内网

安全研究人员Marcus Murray在正在旧金山举行的RSA大会上公布了一种利用恶意JPEG图片入侵企业网络内部Windows服务器的新方法。  攻击流程及漏洞分析 最近,安全专家兼渗透测试员Marcus Murray发现了一种利用恶意JPEG图片来攻击Windows服务器的新方法,利用该方法还可以在目标网络中进行特权提升。几天前,在旧金山举行的RSA大会上,该Marcus现场展示了攻击流程,