草庐IT

最长上升子序列（动态规划）

syc_36 2024-04-24 原文

子序列

所谓的子序列就是在原来序列中找出一部分组成的序列。

与子段不同，不需要连续的某一段，但是要保持原序列的先后顺序

最长上升子序列

在子序列的基础上，后一项大于前一项。

                                                                                                                                                         

【题目描述】

【输入格式】

【输出格式】

 

【输入样例】

12
35 42 4 12 29 21 29 11 1 42 43 49

【输出样例】

7

【数据范围】

分析

我们会想到用递推做。

对于递推，我们需要考虑以下几点

  1. 状态，即F[ i ]表示什么
  2. 递推式，即怎么由前面的项推出后面的项
  3. 答案
  4. 初始值

状态

我们给出一组数

方向一（错误）：F[ i ]表示前 i 项的上升子序列的最大长度

那我们把F[ i ]写在第 i 项的上面

 发现F[ i ]都能列出来，但是递推式完全出不来，前项和后项根本无法递推

方向二：F[ i ]表示以第 i 项为结尾的上升子序列的最大长度

得到：

这就可以递推了

如果a[ j ] < a[ i ]，那就可以形成上升子序列，则F[ i ]为F[ j ]+1和自己本身的较大数

如此循环，那

递推式

就很清楚了，就是：

答案

显而易见，F[ i ]中的最大值

初始值

如果都不符合a[ j ] < a[ i ]，那么F[ i ]就是1

所以初始值是1而不是0

最后最后，

附上代码

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

long long a[5010];
int f[5010];
//f[i]表示以第i项结尾的最长上升子序列
int main()
{
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	int maxn = 0;
	for(int i = 1;i <= n;i++)
	{
		f[i] = 1;//初值
		for(int j = 1;j <= i - 1;j++)
		{
			if(a[j] < a[i])
				f[i] = max(f[i],f[j] + 1);
			maxn = max(maxn,f[i]);
		}
	}
	cout << maxn;
	return 0;
}

最长上升x-oss-processcolor_FFFFFFxff0cc++动态规划

有关最长上升子序列（动态规划）的更多相关文章

  1. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  2. ruby - 在 Ruby 中动态创建数组 - 2

    有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.

  3. ruby - 是否可以将 IRB 提示配置为动态更改？ - 2

    我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO

  4. ruby - 在 Ruby 中比较序列 - 2

    假设我必须(小型到中型)阵列:tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]如何确定tokens是否以相同的顺序包含template的所有条目？(请注意，在上面的示例中，应忽略第一个“ccc”，从而由于最后一个“ccc”而导致匹配。) 最佳答案 这适用于您的示例数据。tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]po

  5. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

  6. ruby - 在 Ruby 中动态生成多维数组 - 2

    我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常，但在我的实际使用中，我不会事先知道需要多少个数组。有一个更好的方法吗？谢谢 最佳答案 不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]

  7. ruby-on-rails - 使用 gmaps4rails 动态加载谷歌地图标记 - 2

    如何只加载map边界内的标记gmaps4rails？当然，在平移和/或缩放后加载新的。与此直接相关的是，如何获取map的当前边界和缩放级别？ 最佳答案 我是这样做的，我只在用户完成平移或缩放后替换标记，如果您需要不同的行为，请使用不同的事件监听器:在你看来(index.html.erb):{"zoom"=>15,"auto_adjust"=>false,"detect_location"=>true,"center_on_user"=>true}},false,true)%>在View的底部添加:functiongmaps4rail

  8. ruby - 动态方法链？ - 2

    如何在对象上调用方法名称的嵌套哈希？例如，给定以下哈希:hash={:a=>{:b=>{:c=>:d}}}我想创建一个方法，给定上面的散列，执行以下操作:object.send(:a).send(:b).send(:c).send(:d)我的想法是我需要从一个未知的关联中获取一个特定的属性(这个方法不知道，但程序员知道)。我希望能够指定一个方法链来以嵌套哈希的形式检索该属性。例如:hash={:manufacturer=>{:addresses=>{:first=>:postal_code}}}car.execute_method_hash(hash)=>90210

  9. ruby-on-rails - 在 Elastic Beanstalk 上升级 Ruby - 2

    如何在ELB上设置和更新ruby​​版本？我已经在我们的qa和暂存环境中使用ruby2.2.2大约8个月了。我刚刚在星期一设置我们的生产环境，它不会部署，因为它说ruby​​设置为2.2.3而我的gemfile说2.2.2。我更新并重新部署，一切似乎都很好。我回到了qa/staging环境，但无法将其更新到ruby​​2.2.3。一直说ruby版本是2.2.2，Gemfile是2.2.3我升级了(通过elbui):运行Ruby2.2(PassengerStandalone)的64位AmazonLinux2015.03v1.3.1到运行Ruby2.2(PassengerStandalon

  10. ruby - 如何使用 method_missing 动态声明方法？ - 2

    我有一个ruby​​程序，我想接受用户创建的方法，并使用该名称创建一个新方法。我试过这个:defmethod_missing(meth,*args,&block)name=meth.to_sclass我收到以下错误:`define_method':interningemptystring(ArgumentError)in'method_missing'有什么想法吗？谢谢。编辑:我以不同的方式让它工作，但我仍然很好奇如何以这种方式做到这一点。这是我的代码:defmethod_missing(meth,*args,&block)Adder.class_evaldodefine_method

随机推荐