题目
题目链接
题解动态规划(最长上升子序列)。
求一个先递增再递减的子序列的最大长度。
一般思路:枚举中间单调性发生变化的位置,分别计算左侧的最长递增子序列长度和右侧最长递减子序列长度,记录二者之和的最大值。
优化做法:预处理记录下每个位置对应的左侧的最长递增子序列长度和右侧最长递减子序列长度。枚举中间单调性发生变化的位置时只需要进行加法和比较运算即可,所以枚举的时间复杂度为 O ( n ) O(n) O(n),最终算法的复杂度由 O ( n 2 ) O(n^2) O(n2)的最长上升子序列算法决定。
代码 O(n^2)// http://bailian.openjudge.cn/practice/2995/
#include
using namespace std;
const int N = 1100;
int f[N], g[N]; // f[i]表示景点1~i的最长上升子序列的长度;g[i]表示景点i~n的最长上升子序列的长度 // 预处理时间变成n^2
int a[N], n, ans;
int main()
{
cin >> n;
for (int i = 1;i > a[i];
for (int i = 1;i t;j --) {
if (a[t] > a[j])
g[t] = max (g[t], g[j] + 1);
}
}
for (int i = 1;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?