当前位置: 代码迷 >> 综合 >> D. Remove One Element(cf)dp
  详细解决方案

D. Remove One Element(cf)dp

热度:55   发布时间:2023-11-23 05:52:18.0

 原题链接:Problem - 1272D - Codeforces

题目大意:给你n个数,求最长连续严格增加的子序列。当然,你可以总共删除一个数或者不删,但是有可能删除一个数之后答案会增加。

先前想的是看每个数取与不取,但是发现一个问题,整个数列最多只能删除一个数。其实想想看, 如果a[i] < a[i + 2],a[i +1]可能会有阻挡也可能没有,可能删除了之后会更新答案,所以可以取原先所有连续递增的最长子序列长度,然后从前往后遍历,如果a[i] < a[i + 2],res = max(res, qian[i] + hou[i + 2]) //qian[i]:以i为最后一个数的最长连续递增子序列;hou[i]:以i为开头的最长连续递增子序列。

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))const int N = 2e5 + 10;
int qian[N], hou[N];
int a[N];int main(){int n;cin >> n;rep(i, n) cin >> a[i];int res = 0;rep(i, n){if(a[i] > a[i - 1]) qian[i] = qian[i - 1] + 1;else qian[i] = 1;res = max(res, qian[i]);}hou[n] = 1;for(int i = n - 1; i >= 1; i--){if(a[i] < a[i + 1]) hou[i] = hou[i + 1] + 1;else hou[i] = 1;}for(int i = 1; i <= n - 2; i++){if(a[i] < a[i + 2]) res = max(res, qian[i] + hou[i + 2]);}cout << res;
}

  相关解决方案