BZOJ 2124等差子序列 线段树&&hash
【题目描述 Description】给一个 1 到 N 的排列{Ai}，询问是否存在 1<=p1<p2<p3<p4<p5<…<pLen<=N（Len>=3），使得 Ap1,Ap2,Ap3,…ApLen 是一个等差序列。【输入描述 Input De...
Ex 6_1 和最大的相连子序列..._第五次作业
设数值列表a0,a1 . . . an存放在数组arr[0. . .n]中. sum[0],sum[1],sum[2] . . . .sum[n]为以该下标为终点元素的连续子序列的和的最大值，则sum[i]=max{sum[i-1]+arr[i],arr[i]} package org.xiu68....
POJ 1631 Bridging signals DP(最长上升子序列)
最近一直在做《挑战程序设计竞赛》的练习题，感觉好多经典的题，都值得记录。题意：给你t组数据，每组数组有n个数字，求每组的最长上升子序列的长度。思路：由于n最大为40000，所以n*n的复杂度不够了，会超时。书上状态方程换成了d[i]——以长度为i+1的上升子序列中末尾元素的最小值。那么我们在遍历第i...
HDU 1069 Monkey and Banana(最长递减子序列)
题目链接题意：摞长方体，给定长方体的长宽高，个数无限制，可随意翻转，要求下面的长方体的长和宽都大于上面的，都不能相等，问最多能摞多高。题解：个数无限，其实每种形态最多就用一次，把每种形态都单独算一种，同时保证长比宽大，按dp做即可。注意要从小到大摞，从大到小是不对的。#include <bit...
LCS最长公共子序列（最优线性时间O(n)）
这篇日志主要为了记录这几天的学习成果。最长公共子序列根据要不要求子序列连续分两种情况。只考虑两个串的情况，假设两个串长度均为n.一，子序列不要求连续。(1)动态规划（Ｏ(n*n)）（转自：http://www.cnblogs.com/xudong-bupt/archive/2013/03/15/29...
51nod 1202 子序列个数
1202 子序列个数 题目来源： 福州大学 OJ基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注子序列的定义：对于一个序列a=a[1],a[2],......a[n]。则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列，其中1&...
hdu 1160 FatMouse's Speed (最长上升子序列+打印路径)
Problem DescriptionFatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mi...
最长回文子序列(LPS)
问题描述：回文是正序与逆序相同的非空字符串，例如“civic”、“racecar”都是回文串。任意单个字符的回文是其本身。求最长回文子序列要求在给定的字符串中找出最长的回文子序列（即找出的序列不要求在原序列中连续）。例如，序列A=“javaej”，其最长回文子序列为“javaj”，长度为5。递推关系...
ACM—最大连续子序列（HDOJ1003）
HDOJ链接 http://acm.hdu.edu.cn/showproblem.php?pid=1003 不了解题目的朋友可以先看一下题目，在这里就不再详细介绍了。（文章内容和解题思路不完全相同,方法一、二、三、四没有对sequence 全为负数的情况进行考虑，就不再对代码进行更新了，如果需要可看...
div.2/Bellovin<最长上升子序列>
题意：序列arr[i--n];输出以a[i]为结尾的最长上升子序列。1<=n<=100000;思路：O(n*log(n)),求最长上升子序列。#include<cstdio>#include<cstring>#include<iostream>#inc...
fzuoj Problem 2129 子序列个数
http://acm.fzu.edu.cn/problem.php?pid=2129Problem 2129 子序列个数Accept: 162 Submit: 491Time Limit: 2000 mSec Memory Limit : 32768 KB Problem Descrip...
Codeforces Round #345 (Div. 1) D. Zip-line 上升子序列 离线 离散化 线段树
D. Zip-line题目连接：http://www.codeforces.com/contest/650/problem/DDescriptionVasya has decided to build a zip-line on trees of a nearby forest. He wants ...
最长公共子序列（LCS问题）
先简单介绍下什么是最长公共子序列问题，其实问题很直白，假设两个序列X,Y，X的值是ACBDDCB，Y的值是BBDC，那么XY的最长公共子序列就是BDC。这里解决的问题就是需要一种算法可以快速的计算出这个最大的子序列，当然，用最简单的方法就是列出XY全部的子系列然后一个个对比，但这样的时间复杂度是绝对...
【C++】子序列匹配问题
/*一个串的“子序列”(subsequence)是将这个串中的一些字符提取出来得到一个新串，并且不改变它们的相对位置关系。例如，串"XDoi","XianYu!","TaiQiangLa!","loa"都是串"XianYuDalaoTaiQiangLa!"的子序列。我们说串t是串s1和s2的公共子序...
nlog(n)解动态规划--最长上升子序列(Longest increasing subsequence)
最长上升子序列LIS问题属于动态规划的初级问题，用纯动态规划的方法来求解的时间复杂度是O(n^2)。但是如果加上二叉搜索的方法，那么时间复杂度可以降到nlog(n)。 具体分析参考：http://blog.chinaunix.net/uid-26548237-id-3757779.html 代码：#...
Luogu 2766 - 最长不下降子序列问题 - [LIS问题][DP+网络流]
题目链接：https://www.luogu.org/problemnew/show/P2766题解（大量参考https://blog.csdn.net/ZscDst/article/details/82423342）：第一问，可以用DP求解，用 $f[i]$ 表示以 $a[i]$ 为结尾的最长不减...
51nod1376 最长上升子序列的数量
机房的人问我树状数组怎么做这题......树状数组维护$len, num$表示$LIS$的长度和数量即可复杂度$O(n \log n)$注：$O(n \log n)$二分+单调栈才是真神仙具体看代码#include <cstdio>#include <cstring>#inc...
洛谷P1439 【模板】最长公共子序列
题目描述给出1-n的两个排列P1和P2，求它们的最长公共子序列。输入输出格式输入格式：第一行是一个数n，接下来两行，每行为n个数，为自然数1-n的一个排列。输出格式：一个数，即最长公共子序列的长度输入输出样例输入样例#1： 复制53 2 1 4 51 2 3 4 5输出样例#1： 复制3说明【数据规...
最长上升子序列的变形（N*log（N））hdu5256
序列变换Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 820 Accepted Submission(s): 336Problem ...
POJ 1458 Common Subsequence(最长公共子序列LCS)
POJ1458 Common Subsequence(最长公共子序列LCS)http://poj.org/problem?id=1458题意:给你两个字符串, 要你求出两个字符串的最长公共子序列长度.分析:本题不用输出子序列,非常easy,直接处理就可以.首先令dp[i][j]==x表示A串的前i个...