首页 > 代码库 > HDU 5489 Removed Interval (LIS变形)
HDU 5489 Removed Interval (LIS变形)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5489
给你n个数，要删去其中连续的L个，问你删去之后的LIS最大是多少？
我们先预处理出以i下标为开头的LIS，存到数组中。
然后可以枚举长为L的区间，每次移动，左边增加一个，右边删除一个。
最长上升子序列长度 = 窗口右边以右边第一个元素开头的最长上升子序列 + 窗口左边最大元素小于窗口右边第一个元素的最长上升子序列。
比如 1 2 [4 3] 2 3 5 , LIS = 3 + 1 = 4
求以i开头的LIS 只要倒着求最长下降子序列 or 倒着a[i]变负求最长上升子序列即可。
代码写的有点乱。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1e5 + 5;17 int dp1[N], dp2[N], a[N], inf = 1e9 + 7;18 int y[N], x[N]; // y[i]表示以i下标为开头的LIS，x[i]表示以i为结尾的LIS19 20 int main()21 {22 int t, n, m;23 scanf("%d", &t);24 for(int ca = 1; ca <= t; ++ca) {25 scanf("%d %d", &n, &m);26 for(int i = 1; i <= n; ++i) {27 scanf("%d", a + i);28 dp1[i] = dp2[i] = inf;29 }30 dp2[0] = dp1[0] = inf;31 int ans = 0; 32 for(int i = n; i >= 1; --i) { //倒着求变负，求以i开头的LIS33 int pos = lower_bound(dp2, dp2 + n, -a[i]) - dp2;34 y[i] = pos + 1;35 //cout << y[i] << endl;36 dp2[pos] = -a[i];37 if(i == m + 1) {38 ans = lower_bound(dp2, dp2 + n, inf) - dp2;39 }40 }41 //cout << ans << endl;42 for(int i = 1; i <= n; ++i) {43 int pos = lower_bound(dp1, dp1 + n, a[i]) - dp1;44 x[i] = pos + 1;45 dp1[pos] = a[i];46 if(i == n - m) {47 ans = max(int(lower_bound(dp1, dp1 + n, inf) - dp1), ans);48 break;49 }50 }51 //cout << ans << endl;52 printf("Case #%d: ", ca);53 dp1[0] = inf;54 for(int i = 1; i <= n; ++i) {55 dp1[i] = inf;56 }57 for(int i = m + 1; i <= n; ++i) {58 int pos = lower_bound(dp1, dp1 + n, a[i] - 1) - dp1; //求滑窗左边刚好小于滑窗右边第一个数的LIS59 ans = max(ans, y[i] + (a[i] - 1 == a[pos] ? pos + 1 : pos));60 *lower_bound(dp1, dp1 + n, a[i - m]) = a[i - m];61 }62 printf("%d\n", ans);63 }64 return 0;65 }
HDU 5489 Removed Interval (LIS变形)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。