[蓝桥杯2022初赛] 最长不下降子序列python
时间: 2023-05-03 22:02:55 浏览: 70
最长不下降子序列问题是在一个序列中寻找一个不下降子序列,该子序列的元素在原序列中的位置是单调递增的,且该子序列的长度最长。
在Python中,我们可以使用动态规划算法来解决这个问题。我们定义一个列表dp,其中dp[i]表示以第i个元素为结尾的最长不下降子序列的长度。
例如,对于序列nums=[1, 2, 3, 1, 2, 3, 4, 5],初始化dp=[1, 2, 3, 1, 2, 3, 4, 5]。因为任何一个元素本身就是一个长度为1的不下降子序列。
接下来,我们遍历序列nums,对于每一个nums[i],我们从0到i-1的元素中寻找比nums[i]小的最大的dp[j],然后dp[i]=dp[j]+1。
最后,我们返回dp中的最大值即可。步骤演示如下:
nums=[1, 2, 3, 1, 2, 3, 4, 5]
dp=[1, 2, 3, 1, 2, 3, 4, 5]
for i in range(1, len(nums)):
for j in range(i):
if nums[j] <= nums[i]:
dp[i] = max(dp[i], dp[j]+1)
max_length = max(dp)
print(max_length)
输出结果为5,即最长不下降子序列的长度为5。
总之,最长不下降子序列问题是一道经典的动态规划问题,在Python中可以使用dp列表来解决。
相关问题
少儿蓝桥杯python组初赛怎么准备
少儿蓝桥杯是国内著名的计算机大赛,作为一个Python组选手,准备充分是获得好成绩的关键。这里提供一些准备建议:
1.熟悉Python语言基础知识,如数据类型、变量、运算符、条件语句、循环语句等。掌握Python基础语法是做题的基础。
2.多练习编程题目,可以从教材、网上或书籍中找到相关练习题。多做一些编程实战题,可以更好地锻炼自己的编程思维和解决问题的能力。
3.了解一些比较常用的Python模块,如math、random、time等,了解它们的基本方法和使用场景。同时,也要了解Python的内置函数和常用模块的语法规则。
4.熟悉蓝桥杯的规则和考试形式,了解题型和考试难度,并根据自己实际水平制定学习计划。
5.多参加蓝桥杯的模拟考试,与其他选手比较,查找自己的不足,针对性地练习和提高。
总之,少儿蓝桥杯Python组初赛需要我们扎实的基础和不断的练习,不能心浮气躁。通过不断的努力,相信我们一定能够取得好成绩!
[蓝桥杯2018初赛]倍数问题
题目描述
输入一个整数n,输出1~n中所有是3或5的倍数的数的和。
输入格式
一个整数n。
输出格式
一个整数,表示满足条件的数的和。
数据范围
1≤n≤10000
输入样例
16
输出样例
60
算法
(暴力枚举) $O(n)$
枚举1~n中每个数,如果是3或5的倍数则加入答案中。
时间复杂度
暴力枚举,时间复杂度 $O(n)$。
空间复杂度
只需要常数个变量,空间复杂度 $O(1)$。
Java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = 0;
for (int i = 1; i <= n; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i;
}
}
System.out.println(sum);
}
}
Python 代码
n = int(input())
sum = 0
for i in range(1, n + 1):
if i % 3 == 0 or i % 5 == 0:
sum += i
print(sum)
C++ 代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i;
}
}
cout << sum << endl;
return 0;
}