题目链接：点击打开链接
有的同学是用线段树来解决的，不过该题是最长递增序列的推广，所以我首先想到的是用DP来解决。
一、原始DP方法
有一种简单的DP思路，很容易想到，不过时间复杂度为O(n^2)提交后会超时，为了便于理解后面的算法，我这里还是先介绍该方法。
题意很简单就不多讲了，不过有一点需要注意，那就是题目给的S序列中可能会有重复元素。
约定：用数组seq[0...n - 1] 存储S序列，dp[0....n - 1]表示dp值， n,d 的意义如题目中的描述
1、定义状态：
dp[i]表示以第i个元素为结尾的满足要求的子串最大的长度。
2、初始化：
初始dp[i] = 1 (0<= i < n)，请读者自己思考为什么
3、状态转移：
dp[i] = max{dp[j] + 1 | i - j > d && seq[i] > seq[j]}
4、代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = (int)1e5 + 10;
struct Elem
{
int val, index;
bool operator < (const Elem& e) const
{
if(val != e.val)
return val < e.val;
else
return index > e.index;
}
};
Elem seq[maxn];
int dp[maxn];
int n,d;
int main(void)
{
//freopen("f:\\code\\file\\data.txt", "r", stdin);
while(scanf("%d%d", &n, &d) == 2)
{
for(int i = 0; i < n; i ++)
{
scanf("%d", &seq[i].val);
seq[i].index = i;
dp[i] = 1;
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < i - d; j ++)
{
if(seq[i].val > seq[j].val)
dp[i] = max(dp[i], dp[j] + 1);
}
}
printf("%d\n", *max_element(dp, dp + n));
}
return 0;
}
5、运行结果：
超时
二、优化到O(nlogn)的方法
如何减小算法的时间复杂度呢？这里我参照的是最长递增序列中的方法，具体优化思想，见我的另一篇博客点击打开链接
1、主要思想：
（1）记录每个元素的值和下标。（2）排序，按键值从小到大，下标从大到小进行排序。（至于为什么这样？请读者理解我上面那篇博客的思想之后，自己思考，因为描述的话很复杂）
2、需要注意的问题：
因为S序列中可能会有重复元素，所以在排序时如果值相同，则按下表从大到小的顺序排列
3、代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = (int)1e5 + 10;
struct Elem
{
int val, index;
bool operator < (const Elem& e) const
{
if(val != e.val)
return val < e.val;
else
return index > e.index;
}
};
bool cmp(const Elem& e1, const Elem& e2)
{
return e1.index < e2.index;
}
Elem seq[maxn];
Elem dp[maxn];
int n, d;
int main(void)
{
// freopen("f:\\code\\file\\data.txt", "r", stdin);
while(scanf("%d%d", &n, &d) == 2)
{
for(int i = 0; i < n; i ++)
{
scanf("%d", &seq[i].val);
seq[i].index = i;
}
sort(seq, seq + n);
dp[0] = (struct Elem){-maxn, -maxn};
int m = 1;
for(int i = 0; i < n; i ++)
{
int tmp = upper_bound(dp, dp + m, seq[i], cmp) - dp;
if(tmp == m)
{
if(seq[i].index - dp[m - 1].index > d && seq[i].val != dp[m - 1].val)
dp[m ++] = seq[i];
}
else
{
if(seq[i].index - dp[tmp - 1].index > d && seq[i].val != dp[tmp - 1].val)
dp[tmp] = seq[i];
}
}
printf("%d\n", m - 1);
}
return 0;
}
4、运行结果：
Accepted