成都专业网站设计公司湖州南浔建设局网站

C
求最长似递增子序列 是子序列！
我误以为是最长上升子序列的变式，但是这个题目和那个题目，并不是很一样

我们选择观察样例： 1 2 4 3 3 5 6 2 1

其实样例当中就给我们了答案，我们能感觉的出来，应该是用长度去减去一个东西，但是应该减去一个什么东西呢，【4，6】之间，这个是3，虽然说第二个三看起来在序列当中是一个不合格的元素但是实际上在这里是一个合格的元素，对于我们选定的区间而言，我们其实是没有必要去追求前两个的，前两个一定是符合要求的，所以我们需要看的是在我们选定的区间抛出前两个元素之后剩下的元素当中不符和要求的最长的子序列，此处是一个子序列！！

#include <iostream>
using namespace std;
const int N = 200000 + 10;
int a[N];
int s[N];
int main(){int n;int k;cin >> n >> k;for(int i = 1;i <= n;i ++) cin >> a[i];for(int i = 3;i <= n;i ++){if(a[i] <= a[i - 1] && a[i - 1] <= a[i - 2]){s[i] = 1;}}for(int i = 1;i <= n;i ++) s[i] += s[i - 1];while(k --){int l,r;cin >> l >> r;if(r - l + 1 <= 2) cout << r - l  + 1<< endl;else cout << (r - l + 1) - s[r] + s[l + 1] << endl;}return 0;
}