最长递增子序列 动态规划 (附带三种子序列更改方法)
题目(1)
时间限制: 1000 ms
内存限制: 64 MB
代码长度限制: 16 KB
简单分析
1.最长递增子序列,最长递减子序列,最长不下降子序列,最长不上升子序列,都是一个模子里刻出来的玩意,动态规划即可。
2.以这个数结尾的最长子序列都是由前面的元素组成的,可以得到动态方程 dp[a] = max{dp[n] + 1}(a > n && D(a) > D(n))(D为所有元素组成的集合)
3.时间复杂度为Θ(n2)。
代码
#include <iostream>
#include <stack>
using namespace std;
int main()
{
//s用于存放路径
stack<int> s;
//data记录序列,sign记录该点为结点的最大子序列长度,before记录该点最大子序列之前结点
//max_int存放最大子序列长度,max_sign存放最大子序列结点,num序列长度
int data[1000],sign[1000], before[1000];
int max_int = 1, max_sign = 0 , num;
//输入数组初始化变量
cin >> num;
for(int tmp = 0; tmp < num; tmp++)
cin >> data[tmp];
before[0] = 0;
sign[0] = 1;
//遍历数组
for(int tmp = 1; tmp < num; tmp++)
{
sign[tmp] = 1;
//查询tmp之前元素,找出他所在子序列位置,并记录之前结点
for(int tmp2 = 0; tmp2 < tmp; tmp2++)
if(data[tmp] > data[tmp2] && sign[tmp2] + 1 > sign[tmp])
{
sign[tmp] = sign[tmp2] + 1;
before[tmp] = tmp2;
}
//如果他比最大的大,就记录下来
if(sign[tmp] > max_int)
{
max_int = sign[tmp];
max_sign = tmp;
}
}
cout << max_int <<endl;
num = 0;
//通过before数组回溯整个遍历过程
while(sign[max_sign] != 1)
{
s.push(data[max_sign]);
max_sign = before[max_sign];
}
//将其输出
cout << data[max_sign];
while(!s.empty())
{
cout << " " << s.top();
s.pop();
}
}
备注
其间最关键的一步是 if(data[tmp] > data[tmp2] && sign[tmp2] + 1 > sign[tmp]) 这句(位于24行)。
剩下三种子序列可以通过更改这段达到
最长递减子序列—— if(data[tmp] < data[tmp2] && sign[tmp2] + 1 > sign[tmp]) ——dp[a] = max{dp[n] + 1}(a < n && D(a) > D(n))
最长不下降子序列—— if(data[tmp] >= data[tmp2] && sign[tmp2] + 1 > sign[tmp])——dp[a] = max{dp[n] + 1}(a >= n && D(a) > D(n))
最长不上升子序列—— if(data[tmp] >= data[tmp2] && sign[tmp2] + 1 > sign[tmp])——dp[a] = max{dp[n] + 1}(a <= n && D(a) > D(n))
(中间是替换语句,后面是动态方程)
题目(2)
时间限制: 1000 ms
内存限制: 64 MB
代码长度限制: 16 KB
简单分析
1.分析与上题区别:不用输出路径,且数据量变大了,因此我们不用保留上个结点的位置,且Θ(n2)的算法是行不通的。
2.由于不用保留路径,所以我们可以开一个数组保存上题sign值相同的结点的最小值,如果后面的数比这个最小值要小,那以他为结点的子序列长度肯定大于最小值的sign。
3.遍历sign的时候采取二分法,可以时间复杂度降为Θ(nlog2n)
代码
#include <iostream>
#include <stack>
using namespace std;
int main()
{
//s用于存放路径
stack<int> s;
//data记录序列,sign记录子序列长度相同的最小值
//max_int存放最大子序列长度,num序列长度
int data[100000],sign[100000];
int max_int = 1, num;
//输入数据并初始化sign
cin >> num;
for(int tmp = 0; tmp < num; tmp++)
cin >> data[tmp];
sign[0] = data[0];
//遍历数组
for(int tmp = 1; tmp < num; tmp++)
{
int high = max_int-1, low = 0;
//先与0和max_int这两个特例进行比较
if(sign[0] > data[tmp])
sign[0] = data[tmp];
else if(sign[max_int-1] < data[tmp])
{
sign[max_int] = data[tmp];
max_int++;
}
//二分遍历side,找出tmp的位置并替换对应变量
else
{
while((high - low) > 1)
{
if(sign[(high + low)/2] > data[tmp])
high = (high + low)/2;
else
low = (high + low)/2;
}
if(sign[low] > data[tmp])
sign[low] = data[tmp];
else if(sign[high] > data[tmp])
sign[high] = data[tmp];
}
}
cout << max_int <<endl;
}
备注
偷个小懒,照着第一题的改法,改掉for循环内的所有比较的符号就行了。