您当前的位置: 首页 > 

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

2995:登山

不牌不改 发布时间:2022-03-12 17:13:50 ,浏览量:0

题目

题目链接

题解

动态规划(最长上升子序列)。

求一个先递增再递减的子序列的最大长度。

一般思路:枚举中间单调性发生变化的位置,分别计算左侧的最长递增子序列长度和右侧最长递减子序列长度,记录二者之和的最大值。

优化做法:预处理记录下每个位置对应的左侧的最长递增子序列长度和右侧最长递减子序列长度。枚举中间单调性发生变化的位置时只需要进行加法和比较运算即可,所以枚举的时间复杂度为 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             
关注
打赏
1662186765
查看更多评论
0.0419s