UVa 1471 防御线（Defense Lines）
发布时间
阅读量：
阅读量
题意：
给出一个长度为n的序列，你的目标是移除一个连续的子序列，使得剩余序列中存在一个最长的连续递增子序列。
详细内容见代码部分。
g数组用于记录以i为结尾的最长递增子序列的长度
f数组用于记录以i为起始的最长递增子序列的长度
所维护的set结构
在维护过程中能够确保满足条件：i < j 且 a[i] < a[j] 且 g[i] < g[j]
代码：
#include<bits/stdc++.h>
#define LL long long
#define ms(s) memset(s, 0, sizeof(s))
#define INF 0x7fffffff
using namespace std;
const int maxn = 2e5 + 10;
int arr[maxn];
int g[maxn]; //which means most length end with i
int f[maxn]; //which means most length begin with i
struct Node {
int a, g; //a means a[i] g means most length end with i
Node(int a, i全部评论 (0)
还没有任何评论哟~