PTA-2023年软件设计综合实践_9(动态规划法)

7-1 数塔

数塔如图所示，若每一步只能走到相邻的结点（图中有数字的方格），则从最顶层走到最底层所经过的所有结点的数字之和最大是多少？测试数据保证结果不大于231−1。

数塔1.png

 C++

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

int main(){
    int n;
    cin>>n;
    while(n--){
        int a[101][101]={0};
        int dp[101][101]={0};
        int high;//最高层号
        cin>>high;
        for(int i=1;i<=high;i++){
            for(int j=1;j<=i;j++){
                cin>>a[i][j];
                if(i==high){
                    dp[i][j]=a[i][j];//递推边界
                }
            }
        }
        for(int i=high-1;i>=1;i--){
            for(int j=1;j<=i;j++){
                dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
            }
        }
        cout<<dp[1][1]<<endl;
    }  
}

7-2 最大子列和问题

给定K个整数组成的序列{ N1​, N2​, ..., NK​ }，“连续子列”被定义为{ Ni​, Ni+1​, ..., Nj​ }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

  • 数据1：与样例等价，测试基本正确性；
  • 数据2：102个随机整数；
  • 数据3：103个随机整数；
  • 数据4：104个随机整数；
  • 数据5：105个随机整数；

输入格式:

#include<iostream>
using namespace std;
 
int main() {
	int K, sum = 0;
	int number[100000];
 
	cin >> K;
 
	for (int i = 0; i < K; i++) {
		cin >> number[i];
	}
 
	for (int i = 0; i < K; i++) {
		int temp = 0;
		for (int j = i; j < K; j++) {
			temp += number[j];
 
			if (temp > sum) {
				sum = temp;
			}
		}
	}
 
	cout << sum;
 
	return 0;
}

7-3 最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
    cin >> n >> m >> a + 1 >> b + 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) {
                //找到一个公共字符，故长度加1
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {
                //没找到则找到临近最大的一个长度，表示最大长度还没有变化
                //【为什么只需要找临近呢？因为dp数组中抽象地保存之前的状态，所以已经包含前面比较短的情况，再者，因为保存之前的状态，现在遍历到的这个位置，临近的元素就是之前状态的长度，因为我现在需要长度不变，所以在临近找一个最大的即可。】
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
  cout << f[n][m] << '\n';
  return 0;
}

7-4 jmu-ds-最长公共子串

给出2个字符串，输出2字符串的最长公共子串。

输入格式:

输入2个字符串，不可包含空格。

输出格式:

输出2个字符串的最长公共子串。若没有公共子串，则输出“NULL”

python

a = input()
b = input()
def maxSubstring(a,b):
    if a==None or b==None:#空值返回
        return None
    #接下来获取两者较长和较短的字符串
    if len(a)>len(b):
        M=a
        m=b
    else:
        M=b
        m=a
    #遍历遍历较短的字符串，并依次减少短字符串的字符数量，
    #判断长字符是否包含该子串
    i=0
    while i<len(m):
        begin=0
        end=len(m)-i
        #先扣住end部分的字符，然后一个循环看begin从0~end是否有符合的最大串
        while end<=len(m):
            current=m[begin:end]
            if current in M:
                return current
            begin+=1
            end+=1
        i+=1
    return 'NULL'
print(maxSubstring(a,b))

7-5 最长有序子序列

对于给定一个数字序列 (a1​，a2​，…，an​) ，如果满足a1​<a2​<…<an​，则称该序列是有序的。若在序列(a1​，a2​，…，an​) 中删除若干元素得到的子序列是有序的，则称该子序列为一个有序子序列。有序子序列中长度最大的即为最长有序子序列。

例如，(1，3，5)、(3，5，8)、(1，3，5，9)等都是序列 (1，7，3，5，9，4，8) 的有序子序列；而(1，3，5，9)、(1，3，5，8)、(1，3，4，8)都是序列 (1，7，3，5，9，4，8)的一个最长有序子序列，长度为4。

请编写程序，求出给定数字序列中的最长有序子序列的长度。

python

def longest_ordered_subsequence(nums):
    # 获取数字序列的长度
    n = len(nums)
    
    # 创建一个数组来保存以每个元素结尾的最长有序子序列的长度
    dp = [1] * n
    
    # 计算最长有序子序列的长度
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    # 返回最长有序子序列的最大长度
    return max(dp)

# 读取输入数据的数量
T = int(input())

for _ in range(T):
    # 读取数字序列的长度和元素
    n = int(input())
    sequence = list(map(int, input().split()))
    
    # 计算并输出最长有序子序列的长度
    result = longest_ordered_subsequence(sequence)
    print(result)
    
    # 输出空行（除了最后一组测试数据）
    if _ != T - 1:
        print()

7-6 跳房子

跳房子是小朋友玩的游戏。地面上画出一连串格子，每个格子里有一个整数，小朋友从外面跳入格子，并继续往前跳，直到跳出所有格子。每次跳跃的规则是，可以跳入下一格或下下格或下下下格。怎么跳能让落脚格子里的数的累加和最小。

python3

n = int(input())  # 读入格子数  
nums = list(map(int, input().split()))  # 读入每个格子里的数
nums=nums+[0]

dp = [100000] * (n + 2)  # 初始化dp数组
dp[0] = 0   
dp[1] = nums[0]
  
for i in range(2, n + 2 ):  
    dp[i] = min(dp[i - 1] + nums[i-1], dp[i - 2] + nums[i-1], dp[i - 3] + nums[i-1])  # 计算当前格子的最小累加和  
  
print(dp[n+1])  # 输出结果

7-7 寻宝路线

在一个m行n列方格矩阵中，每一个方格内摆放着价值不等的宝贝（价值可正可负），让小明感到好奇的是，从左上角到达右下角的所有可能路线中，能捡到宝贝的价值总和最大是多少？而且这种达到最大值的路线
又有多少条？【注意：只能从一个格子向下或向右走到相邻格子，并且走到的格子宝贝一定会被捡起。】

c++

#include <iostream>
#include <vector>

using namespace std;

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

    vector<vector<int>> grid(m, vector<int>(n, 0));

    // 读取宝贝价值矩阵
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];
        }
    }

    // 创建动态规划所需的二维数组
    vector<vector<int>> dp(m, vector<int>(n, 0));
    vector<vector<int>> ways(m, vector<int>(n, 0));

    dp[0][0] = grid[0][0];
    ways[0][0] = 1;

    // 初始化第一列和第一行
    for (int i = 1; i < m; ++i) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
        ways[i][0] = 1;
    }

    for (int j = 1; j < n; ++j) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
        ways[0][j] = 1;
    }

    // 计算其余位置的最大值和路径数量
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (dp[i - 1][j] > dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j] + grid[i][j];
                ways[i][j] = ways[i - 1][j];
            } else if (dp[i - 1][j] < dp[i][j - 1]) {
                dp[i][j] = dp[i][j - 1] + grid[i][j];
                ways[i][j] = ways[i][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j] + grid[i][j];
                ways[i][j] = ways[i - 1][j] + ways[i][j - 1];
            }
        }
    }

    int max_value = dp[m - 1][n - 1];
    int max_ways = ways[m - 1][n - 1];

    cout << max_value << " " << max_ways << endl;

    return 0;
}

7-8 硬币找零

用 n 种不同币值的硬币凑出 m 元，最少需要多少硬币。

输入格式:

第一行输入需要凑的钱数 m 和硬币的种类 n （0<m<100，0<n<10），第二行输入 n 种硬币的具体币值，假设硬币供应量无限多。

输出格式:

输出最少需要的硬币个数

输入样例:

在这里给出一组输入。例如：

PYTHON3

def min_coins(coins, m):
    dp = [float('inf')] * (m + 1)
    dp[0] = 0

    for i in range(1, m + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[m] if dp[m] != float('inf') else -1

if __name__ == "__main__":
    m, n = map(int, input().split())
    coins = list(map(int, input().split()))

    result = min_coins(coins, m)
    print(result)

7-9 至多删三个字符

给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？

C++

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int dp[N][4];
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	string s, stemp;
	cin >> stemp;
	s.assign("0");
	s.append(stemp);
	dp[0][0] = 1;
	for (int i = 1; i < s.size(); ++i)
	{
		for (int j = 0; j <= 3; ++j)
		{
			dp[i][j] = dp[i - 1][j];
			if (j)
				dp[i][j] = dp[i][j] + dp[i - 1][j - 1];
			for (int k = i - 1; k >= 1 && i - k <= j; --k)
			{
				if (s[k] == s[i])
				{
					dp[i][j] = dp[i][j] - dp[k - 1][j - (i - k)];
					break;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= 3; ++i)
	{
		ans = ans + dp[s.size() - 1][i];
	}
	cout << ans << endl;
	return 0;
}

7-10 拼题A打卡奖励

拼题 A 的教超搞打卡活动，指定了 N 张打卡卷，第 i 张打卡卷需要 mi​ 分钟做完，完成后可获得 ci​ 枚奖励的金币。活动规定每张打卡卷最多只能做一次，并且不允许提前交卷。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币？

输入格式：

输入首先在第一行中给出两个正整数 N（≤103） 和 M（≤365×24×60），分别对应打卡卷的数量和以“分钟”为单位的活动总时长（不超过一年）。随后一行给出 N 张打卡卷要花费的时间 mi​（≤600），最后一行给出 N 张打卡卷对应的奖励金币数量 ci​（≤30）。上述均为正整数，一行内的数字以空格分隔。

C++

#include<bits/stdc++.h>
using namespace std;
const int N=1004;
const int INF=0x3f3f3f3f;
int n,m;
int w[N],v[N];
//int f[N][10000];
int dp[N][30005];//前i个物品中得到价值为j时候的最小花费 //ans为dp[n][j]<m时最大的j 
int mv=0;

int main()
{
//	cout<<365*60*24;
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>w[i];
	for(int i=1;i<=n;++i){
		cin>>v[i];
		mv+=v[i];
	}

// 01背包写法，空间不够，而且也会超时，因为“花费”这一维度规模比较大，而递推时需要一一枚举
//		for(int i=1;i<=n;++i)
//		for(int j=0;j<=m;++j)
//		{
//			if(j>=w[i])
//			f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
//			else f[i][j]=f[i-1][j];
//		}
		

//下面是另一种思路，第二维换成价值
		//初始化 
		for(int i=0;i<=n;++i)
		{
			for(int j=0;j<=mv;++j){
				
				dp[i][j]=INF; 
			}
		}
		dp[0][0]=0;
		//递归过程：分为取第i个和不取第i个
		for(int i=1;i<=n;++i)
		{
			for(int j=0;j<=mv;++j){
				if(j>=v[i])//注意边界
				dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
				else 
				dp[i][j]=dp[i-1][j];
			}
		}
		//可以改进递推过程：由于递归方程中两个来源都是上一个i的,去掉第一个维度,节省空间，注意这时候j要从大到小迭代，才能保证递推过程中的dp[j-v[i]]是来源于i-1而不是i
// 		for(int i=1;i<=n;++i)
// 		{
// 			for(int j=mv;j>=0;--j)
// 			{
// 				if(j>v[i])
// 				dp[j]=min(dp[j-v[i]]+w[i],dp[j]);
// 				else 
// 				dp[j]=dp[j];
// 		}
		//取答案：最小花费在给定的m内的最大价值
		for(int j=mv;j>=0;j--)
		{
			if(dp[n][j]<=m){
				cout<<j;
				break;
			}
		}

//	cout<<f[n][m];
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/201552.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

对属于国家秘密的地理信息的获取、持有、提供、利用情况进行登记并长期保存，实行可追溯管理

对属于国家秘密的地理信息的获取、持有、提供、利用情况进行登记并长期保存，实行可追溯管理

对属于国家秘密的地理信息的获取、持有、提供、利用情况进行登记并长期保存&#xff0c;实行可追溯管理 数据记录&#xff08;包括获取、持有、提供、利用、销毁等全闭环&#xff09;
阅读更多...
Linux安装Java环境

Linux安装Java环境

处理安装环境 检查系统版本 [rootjeven ~]# cat /etc/centos-release CentOS Linux release 7.6.1810 (Core)检查系统内核版本 [rootjeven ~]# uname -r 6.1.8-1.el7.elrepo.x86_64清空卸载java环境&#xff08;如果已经安装了&#xff09; 查询java所在位置 [rootjeven …
阅读更多...
基于SSM框架的图书馆管理系统设计与实现

基于SSM框架的图书馆管理系统设计与实现

基于SSM框架的图书馆管理系统 摘要&#xff1a;在21信息时代中&#xff0c;编程技术的日益成熟&#xff0c;计算机已经是普通使用的。编程技术的实现是基于计算机硬件上&#xff0c;计算机科学与技术的进步&#xff0c;让时代发展的更快&#xff0c;更加信息化。人们都是学习如…
阅读更多...
从0开始学习JavaScript--JavaScript中的解构赋值及使用场景

从0开始学习JavaScript--JavaScript中的解构赋值及使用场景

在现代JavaScript中&#xff0c;解构赋值是一种强大而灵活的语法特性&#xff0c;它允许从数组或对象中提取值并赋给变量。这种语法不仅使代码更简洁&#xff0c;而且提高了可读性。在本篇文章中&#xff0c;将深入探讨JavaScript中解构赋值的基本概念、语法规则以及丰富的使用…
阅读更多...
SQL注入 - CTF常见题型

SQL注入 - CTF常见题型

文章目录 题型一 &#xff08; 字符型注入 &#xff09;题型二 &#xff08; 整数型注入 &#xff09;题型三 &#xff08; 信息收集SQL注入&#xff09;题型四 &#xff08; 万能密码登录 &#xff09;题型五 &#xff08; 搜索型注入文件读写 &#xff09;题型六 &#xff08…
阅读更多...
如何使用 ONLYOFFICE 文档代理功能

如何使用 ONLYOFFICE 文档代理功能

简介 ONLYOFFICE 文档以在线应用程序的方式运行&#xff0c;在很多情形中可能会存在需要将其集成至内部网络的情形。如今&#xff0c;许多内部网络维护者可能会出于某些目的使用不同的 Web 服务器作为代理。此时ONLYOFFICE 文档中的代理功能就能派上用场了。市面上应用最广泛的…
阅读更多...
python安装PyHook3

python安装PyHook3

pyhook 报错 “TypeError: KeyboardSwitch() missing 8 required positional arguments: ‘msg’, ‘vk_code’, ‘scan_code’, ‘ascii’, ‘flags’, ‘time’, ‘hwnd’, and ‘win_name’” 一、PyHook3简介 pyHook包为Windows中的全局鼠标和键盘事件提供回调。Python应…
阅读更多...
实验一 SAS 基本操作和数据表的导入 2023-11-29

实验一 SAS 基本操作和数据表的导入 2023-11-29

一、上机目的 熟悉SAS的集成环境并掌握它的基本操作。理解SAS程序的结构&#xff0c;理解其中的过程&#xff0c;过程选项&#xff0c;语句&#xff0c;语句选项等概念&#xff0c;掌握SAS编程技术。 二、上机内容 主要有SAS操作界面、SAS窗口操作、SAS菜单操作、SAS按钮操作…
阅读更多...
基于yolov2深度学习网络的打电话行为检测系统matlab仿真

基于yolov2深度学习网络的打电话行为检测系统matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1、YOLOv2网络原理 4.2、基于YOLOv2的打电话行为检测 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 .................................…
阅读更多...
python读取excel自动化生成sql建表语句和java实体类字段

python读取excel自动化生成sql建表语句和java实体类字段

1、首先准备一个excel文件&#xff1a; idtypenameidint学号namestring姓名ageint年龄sexstring性别weightdecimal(20,4)体重scoredecimal(20,4)分数 2、直接生成java字段和注释&#xff1a; import pandas as pddf pd.read_excel(test.xlsx, sheet_nameSheet1)for i in ran…
阅读更多...
算法通关第十七关黄金挑战——透析跳跃问题

算法通关第十七关黄金挑战——透析跳跃问题

大家好&#xff0c;我是怒码少年小码。 本篇是贪心思想的跳跃问题专题&#xff0c;跳跃问题出现的频率很高。 跳跃游戏 LeetCode 55&#xff1a;给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。 …
阅读更多...
Mac单独修改应用语言

Mac单独修改应用语言

方法1: 方法2: defaults write com.microsoft.Excel AppleLanguages ("zh-cn") defaults write com.microsoft.Word AppleLanguages ("zh-cn")参考&#xff1a;https://www.zhihu.com/question/24976020
阅读更多...
【BUG合集】（一）①数据库存1/0，请求结果返回true和false；②sql查数据库能查，但mybatis查为空；③data64图片存储为异常；

【BUG合集】（一）①数据库存1/0，请求结果返回true和false；②sql查数据库能查，但mybatis查为空；③data64图片存储为异常；

前言 最近&#xff0c;在工作上接手的任务中&#xff0c;各种 bug 问题出现&#xff0c;在解决的同时也可以记录一下。因此&#xff0c;觉得可以出个记录 bug 合集。方便后来者碰到类似情况&#xff0c;可以作为一个参考进行解决。 文章题目就包含当前文章内容中所遇到的三个 b…
阅读更多...
iMazing是什么软件?2024最新版本如何下载

iMazing是什么软件?2024最新版本如何下载

iMazing是一款功能强大的iOS设备管理软件&#xff0c;它可以帮助用户备份和管理他们的iPhone、iPad或iPod Touch上的数据。除此之外&#xff0c;它还可以将备份数据转移到新的设备中、管理应用程序、导入和导出媒体文件等。本文将详细介绍iMazing的功能和安全性&#xff0c;并教…
阅读更多...
算法通关村-----超大规模数据场景的问题

算法通关村-----超大规模数据场景的问题

对20GB文件进行排序 问题描述 假设有一个20GB的文件&#xff0c;每行一个字符串&#xff0c;请说明如何对这个文件进行排序 问题分析 20GB的文件很难一次加载到内存中&#xff0c;可以采用分块策略&#xff0c;先使块内有序&#xff0c;在使块间有序。 实现思路 按照给定…
阅读更多...
鸿蒙开发已成新趋势

鸿蒙开发已成新趋势

随着华为鸿蒙操作系统的快速崭露头角&#xff0c;鸿蒙开发已然成为当前技术领域的热门新趋势。本文将深入探讨鸿蒙开发的重要性和独特优势&#xff0c;并详细介绍一些关键的鸿蒙开发技术和工具&#xff0c;以及它们对开发者个人和整个行业带来的深远影响。 首先&#xff0c;鸿蒙…
阅读更多...
JOSEF约瑟 逆功率继电器 GG-21 5a 100v 50hz

JOSEF约瑟 逆功率继电器 GG-21 5a 100v 50hz

系列型号 GG-21逆功率继电器 GG-22过载继电器 1 用途 逆功率继电器GG-21/5A/100V 在出现逆功率时&#xff0c;从电网中断开交流发电机。 2 概述 逆功率继电器是基于感应式原理(具有旋转磁场)而工作。 继电器导磁体由两个磁路系统组成&#xff1a;上磁路系统和下磁路系统…
阅读更多...
ubuntu16.04部署gitlab-runner触发gitlab流水线

ubuntu16.04部署gitlab-runner触发gitlab流水线

环境&#xff1a;ubuntu16.04 gitlab服务器&#xff1a;192.168.1.12 runner服务器&#xff1a;192.168.1.11 1.下载 环境&#xff1a;192.168.1.11 cd /usr/local/srcwget https://gitlab-runner-downloads.s3.amazonaws.com/latest/deb/gitlab-runner_amd64.debsudo dpkg …
阅读更多...
2023.11.25 python常用数据集信息查看命令

2023.11.25 python常用数据集信息查看命令

2023.11.25 python常用数据集信息查看命令 在对数据集进行处理前一般需要对数据集先进行一个基本的观察&#xff0c;根据观察结果和经验确定处理方式。以kaggle员工离职数据集为例进行操作。 打印前5条数据 # 导入包 import pandas as pd# 读入数据 df pd.read_csv(HR_comm…
阅读更多...
AIoT智能物联网平台技术架构参考

AIoT智能物联网平台技术架构参考

具体来说&#xff0c;AIoT平台能够实现智能终端设备之间、不同系统平台之间、不同应用场景之间的互融互通&#xff0c;进一步推动万物互联的进程。 AIoT智能物联网平台是结合了人工智能&#xff08;AI&#xff09;和物联网&#xff08;IoT&#xff09;技术的平台。它旨在通过物…
阅读更多...
最新文章

Copyright @ 2022~2023