题目大意是给出一段数字序列,可以忽略一次一段连续的序列,求忽略后的最长连续上升子序列
思路是dp,用end数组记录以当前元素作为结尾的最长连续上升序列的元素个数,那么不难得到状态转移方程为
dp(i) = max(dp(i - 1), max( end[k] ) ) + 1
代码如下:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
using namespace std;
#define LL long long
const int maxn = 200009;
const int INF = 1000000007;
int a[maxn], enda[maxn], d[maxn], g[maxn]; //enda数组记录以当前元素结尾的最长上升连续序列的长度
int main() {
int startt = clock();
freopen("input.txt", "r", stdin);
int t, kase = 0;
scanf("%d", &t);
while(t--) {
int n; scanf("%d", &n);
a[0] = 0; enda[0] = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if(a[i] > a[i - 1]) enda[i] = enda[i - 1] + 1;
else enda[i] = 1;
// printf("%d\n", enda[i]);
}
int ans = 0;
for(int i = 1; i <= n; i++) g[i] = INF; //lis的变形,g[i]表示enda的值为i的最小元素值
for(int i = 1; i <= n; i++) {
int k = lower_bound(g + 1, g + n + 1, a[i]) - g - 1;
if(a[i] > a[i - 1]) d[i] = max(d[i - 1], k) + 1;
else d[i] = k + 1;
ans = max(ans, d[i]);
g[enda[i]] = min(g[enda[i]], a[i]);
// printf("%d\n", d[i]);
}
printf("Case #%d: %d\n", ++kase, ans);
}
int endt = clock();
printf("%d\n", endt - startt);
return 0;
}