洛谷P2766 最长不下降子序列问题（最大流）
传送门第一问直接$dp$解决，求出$len$然后用$f[i]$表示以$i$为结尾的最长不下降子序列长度，把每一个点拆成$A_i,B_i$两个点，然后从$A_i$向$B_i$连容量为$1$的边然后考虑$f[i]$，如果$f[i]==1$，则从$s$向$A_i$连边，如果$f[i]==len$，那么从$...
BZOJ 3173: [Tjoi2013]最长上升子序列 (线段树+BIT)
先用线段树预处理出每个数最终的位置.然后用BIT维护最长上升子序列就行了.用线段树O(nlogn)O(nlogn)O(nlogn)预处理就直接倒着做,每次删去对应位置的数.具体看代码CODE#include<bits/stdc++.h>using namespace std;char c...
bzoj 3173: [Tjoi2013]最长上升子序列【dp+线段树】
我也不知道为什么把题看成以插入点为结尾的最长生生子序列……还WA了好几次先把这个序列最后的样子求出来，具体就是倒着做，用线段树维护点数，最开始所有点都是1，然后线段树上二分找到当前数的位置，把这个点标为0（相当于对于这之前的序列这个点是不存在的），把每个数的位置记为p[i]然后用另一颗线段树维护每个...
Bzoj 3173: [Tjoi2013]最长上升子序列 平衡树,Treap,二分,树的序遍历
3173: [Tjoi2013]最长上升子序列Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1183 Solved: 610[Submit][Status][Discuss]Description给定一个序列，初始为空。现在我们将1到N的数字插入到...
[BZOJ3173][Tjoi2013]最长上升子序列
[BZOJ3173][Tjoi2013]最长上升子序列试题描述给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？输入第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，...
392 Is Subsequence 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符...
【NOIP2017练习】跳跃切除子序列（模拟）
题意： 思路： 已放弃 1 #include <bits/stdc++.h> 2 typedef long long LL; 3 4 int main(){ 5 int T; scanf("%d", &T); 6 while(T--){ 7 ...
最长上升公共子序列
你有一个日志文件，里面记录着各种系统事件的详细信息。自然的，事件的时间戳按照严格递增顺序排列（不会有两个事件在完全相同的时刻发生）。 遗憾的是，你的系统被病毒感染了，日志文件中混入了病毒生成的随机伪事件（但真实事件的相对顺序保持不变）。备份的日志文件也被感染了，但由于病毒采用的随机感染方法，主日志文...
noip2004 合唱队形 （最长严格上升子序列+最长严格下降子序列）
P1098合唱队形Accepted 标签：动态规划 LISNOIP提高组2004描述N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足...
【bzoj 十连测】[noip2016十连测第八场]Problem B: 降雷皇（最长上升子序列+线段树|next数组）
Problem B: [noip2016十连测第八场]降雷皇 Time Limit: 10 Sec Memory Limit: 512 MB Submit: 39 Solved: 20 [ Submit][ Status][ Web Board] Description...
DP（最长上升子序列） HDU-1087
Super Jumping! Jumping! Jumping! Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 36016 Acce...
hdu1025 dp（最长上升子序列LIS）
题意：有一些穷国和一些富国分别排在两条直线上，每个穷国和一个富国之间可以建道路，但是路不能交叉，给出每个穷国和富国的联系，求最多能建多少条路 我一开始在想有点像二分图匹配orz，很快就发现，当我把穷国按顺序排了之后，富国写在它旁边，能够连接的富国就成了一个上升子序列，那么问题来了！上升子序列最长有多...
hdu 1069 Monkey and Banana(dp 最长上升子序列)
http://acm.hdu.edu.cn/showproblem.php?pid=1069 题意：有n种类型的木块，木块是长方体，已知每种长方体的长宽高，且每种木块的数量是无限的。问这些木块能够摞起来的最高高度，摞起来的规则是上面的木块的长和宽必须严格小于下面木块的长和宽。 思路：把每种木块分成六...
hdu1257 dp（最长上升子序列）
题意：有一种拦截系统，可以打击导弹，但是打击的高度会逐渐下降，因此为了防御导弹攻击，就必须用多个系统，现给出一列导弹依次的高度，求最少需要的系统数。 这道题是最长上升子序列问题，但是我一开始其实并没有想到，最开始我的思路是依次剔除最长下降子序列，每剔除一轮就是需要一个拦截系统，然后直到全部数都剔除了...
hdu 4352 数位dp（最长上升子序列的长度为k的个数）
http://acm.hdu.edu.cn/showproblem.php?pid=4352 Problem Description #define xhxj (Xin Hang senior sister(学姐)) If you do not know xhxj, then ca...
【简单DP】 最长上升子序列（个数）
Description A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be...
hdu 3998(最长上升子序列及个数）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3998 思路：可以用n*log(n)的做法求出最长上升子序列，然后删除原数组中的这些数，再求最长上升子序列（如果长度减小，则直接退出）。 View Code 1 #include<iostream...
hdu3998 Sequence（最长上升子序列及其个数）
DescriptionThere is a sequence X (i.e. x[1], x[2], ..., x[n]). We define increasing subsequence of Xas x[i1], x[i2],...,x[ik], which satisfies follow ...
【LeeCode】392. 判断子序列
【题目描述】给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。进阶：如果有大量输入的 S，称作 S1,...
【题解】Luogu P2766 最长不下降子序列问题
原题传送门实际还是比较套路的建图先暴力dp一下反正数据很小第一小问的答案即珂以求出数列的最长不下降子序列的长度s考虑第二问如何做：将每个点拆点从前向后连一条流量为1的边如果以它为终点的最长不下降子序列长度为1，从源点向它（前）连一条流量为1的边如果以它为终点的最长不下降子序列长度为s，从它（后）向汇...