[作业题] #4 CF568E

Longest Increasing Subsequence

题目描述

点此看题

解法

首先有一个关键的 \(\tt observation\)：由于本题求的是最长上升子序列，所以在求解最优解是每个数只出现一次这个限制是可以忽略的，因为最长上升子序列不可能包含重复的数。

考虑魔改一下传统的 \(\tt LIS\) 做法：设 \(f_i\) 表示长度为 \(i\) 的最长上升子序列的结尾最小值，\(g_i\) 表示这个结尾的位置。那么非空位可以直接转移，空位可以双指针转移，暴力枚举所有填入的数即可。

再考虑如何构造出最后的答案，对于非空位我们可以记录 \(l_i\) 表示以 \(i\) 结尾的最长上升子序列长度，\(p_i\) 表示这个最优序列的上一个位置。所以对于非空位我们可以直接跳到上一个位置，对于空位可以直接枚举上一个位置，复杂度没问题，总时间复杂度 \(O((n+m)k)\)

#include 
#include 
#include 
#include 
using namespace std;
const int M = 100005;
const int inf = 0x3f3f3f3f;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,t,a[M],b[M],c[M],lst[M];
int f[M],g[M],l[M],p[M];map mp;
int get(int x)
{
	return b[lower_bound(b+1,b+1+m,x)-b-1];
}
signed main()
{
	n=read();
	for(int i=1,z=0;i<=n;i++)
	{
		a[i]=read();f[i]=inf;
		lst[i]=z;if(a[i]==-1) z=i;
	}
	m=read();
	for(int i=1;i<=m;i++) mp[b[i]=read()]++;
	sort(b+1,b+1+m);
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=-1)
		{
			int j=lower_bound(f+1,f+1+t,a[i])-f;
			p[i]=g[j-1];l[i]=j;
			g[j]=i;f[j]=a[i];
			if(f[t+1]=1;k--)
		{
			while(j>0 && f[j-1]>=b[k]) j--;
			f[j]=b[k];g[j]=i;
		}
		if(f[t+1]=1;k--)
			if(l[k]==nl && a[k]
DP

相关

DP决策优化小结

dp专题练习

腾讯云搭建个人博客wordpress

dp多维状态的优化

CS5265完全替代兼容龙迅LT8711|Type-C/DP1.2 to HDMI2.0方案芯片|CS5265兼容TYPEC手机

Java高并发，ThreadPoolExecutor线程池技术

sqlserver with(NOLOCK) 或 with(READPAST）

单调队列优化DP历险记

CS5262设计DP转HDMI 4K60HZ +VGA 1080P方案芯片

「NOI2020」命运（树形DP+线段树合并）

线程池ThreadPool知识碎片和使用经验速记

阿里面试官常问的TCP和UDP，你真的弄懂了吗？

标签