codeforce 1500
COFO::1272D Remove One Element
cofo problem
COFO::1272D Remove One Element
Problem
- level : 1500
- tag : brute force, dp
- TIME
- to understand :
- to algorithm : fail
- to code :
- to debug :
- understanding edit : 15
Point
- n개의 원소로 이루어진 배열 a 가 주어집니다.
- 여기서 최대 원소 한개를 뺄 수 있을때, strict 한 오름차순의 최대 길이를 출력합니다.
Design
- 구멍이 너무 많은 풀이 방법들만 떠올라서 못 풀었던 것 같습니다.
- 예를들어, a[i-1], a[i], a[i+1] 을 비교하고, a[i] > a[i+1] 즉 drop을 감지한다던지,
- dp는 생각해보았지만, 어떻게 이걸 N^2이 아니게 dp를 짤 수 있는지 떠오르지 않았습니다.
- edit은 깔끔한 풀이를 dp를 통해 제공합니다.
- r[i] : i번째에서 시작하는 가장 긴 오름차순의 길이
- l[i] : i번째에 끝나는 가장 긴 오름차순의 길이
- 이를 통해, a[i]를 제외하는 경우 l[i-1] + r[i+1]로 값을 비교할 수 있습니다.
- 즉, i를 제외하고 O(1)에 연결만 해주는 거죠
Complexity
- O(N)
Code
#include<bits/stdc++.h>
#define sz(v) (int) v.size()
#define all(v) v.begin(), v.end()
#define rep(i, a, b) for(int i=(a); i <(b); i++)
#define r_rep(i, a, b) for(int i=(a); i >(b); i--)
using namespace std;
typedef long long ll;
int n;
ll a[2 * 100001];
ll l[2 * 100001], r[2 * 100001]; // l[i] : ending in i. r[i] : starting from i.
void solve(){
cin >> n;
rep(i, 0, n){
cin >> a[i];
l[i] = r[i] = 1;
}
ll ans = 1;
rep(i, 1, n) if(a[i-1] < a[i]){
l[i] = l[i-1] + 1;
ans = max(ans, l[i]);
}
r_rep(i, n-2, -1) if(a[i] < a[i+1]){
r[i] = r[i+1] + 1;
ans = max(ans, r[i]);
}
rep(i, 1, n-1) if(a[i-1] < a[i+1])
ans = max(ans, l[i-1] + r[i+1]);
cout << ans << '\n';
}
int main(){
solve();
return 0;
}