Codevs 2188 最长上升子序列(变式)

2023-12-25 16:08

本文主要是介绍Codevs 2188 最长上升子序列(变式),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2188 最长上升子序列
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 钻石 Diamond
题目描述 Description
LIS问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子序列,你还能解决吗?
给出一个长度为N整数序列,请求出它的包含第K个元素的最长上升子序列。
例如:对于长度为6的序列<2,7,3,4,8,5>,它的最长上升子序列为<2,3,4,5>,但如果限制一定要包含第2个元素,那么满足此要求的最长上升子序列就只能是<2,7,8>了。
输入描述 Input Description
第一行为两个整数N,K,如上所述。
接下来是N个整数,描述一个序列。
输出描述 Output Description
请输出两个整数,即包含第K个元素的最长上升子序列长度。
样例输入 Sample Input
8 6
65 158 170 299 300 155 207 389
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
80%的数据,满足0<=n<=1000,0<=k<=n
100%的数据,满足0<=n<=200000,0<=k<=n
分类标签 Tags
动态规划

/*
预处理一下.
把没有贡献的值都删掉.
然后能够保证询问的位置在LCS里.
然后我们把问题推广一下.
如果有多个询问位置.
我们就先保证[k1,k2]位置间的任意数x,
使得x满足a[k1]<x<a[k2].
然后二分查找跑LCS就好了.
这里还是用lower_bound().
懒-_-
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 200001
using namespace std;
int n,k,a[MAXN],s[MAXN],tot,ans,c[MAXN];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
void slove()
{//ans=1;for(int i=1;i<=tot;i++){if(s[i]>c[ans]) c[++ans]=s[i];else {int p=lower_bound(c+1,c+ans+1,s[i])-c;c[p]=s[i];}}
}
int main()
{n=read(),k=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<k;i++)if(a[i]<a[k]) s[++tot]=a[i];s[++tot]=a[k];for(int i=k;i<=n;i++) if(a[i]>a[k]) s[++tot]=a[i];slove();printf("%d",ans);return 0;
}

这篇关于Codevs 2188 最长上升子序列(变式)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/536096

相关文章

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10099(floyd变式)

题意: 有一个导游要带着一群旅客从一个城市到达另一个城市,每个城市之间有最大的旅客流量限制。 问最少几趟能将这些旅客从一个城市搞到另一个城市。 解析: 用floyd找出最小流量中的最大边,然后次数就是   ceil(总人数 / 最大承载量 - 1),-1的意思是导游每次也要在车上。 ps.老司机哭晕在厕所 代码: #include <iostream>#includ

uva 10048(floyd变式)

题意: 求两个点之间经过的路径中最大噪声最小的值。 解析: floyd的变式,每次取g[i][k] g[k][j]中的大边与当前边g[i][j]比较,取小。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#includ

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

PHP最长单一子串

<?php//方法一$s='abcccddddddcdefg';$max='';while($s!=''){$i=0; while($i<strlen($s) && $s[$i]==$s[0]) $i++;if ($i>strlen($max)){$max=substr($s,0,$i);} $s=substr($s,$i);}echo $m