[NOIP 시뮬레이션 문제] Incr(dp)
2286 단어 IP
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mkpii make_pair<int, int>
#define pdi pair<double, int>
#define mkpdi make_pair<double, int>
#define pli pair<ll, int>
#define mkpli make_pair<ll, int>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define error(x) (!(x)?puts("error"):0)
#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; }
const int N=1e5+10;
int n, g[N], f[N], a[N], ans;
int main() {
read(n);
for1(i, 1, n) read(a[i]);
CC(g, 0x7f);
for1(i, 1, n) {
int t=lower_bound(g+1, g+1+i, a[i])-g;
f[i]=t;
g[t]=a[i];
ans=max(ans, t);
}
printf("%d", n-ans);
return 0;
}
[제목 묘사]
수열 A1, A2,......,AN, 최소 숫자를 수정하여 수열이 엄격하게 단조롭게 증가합니다.
[형식 입력]
1 행, 1 정수 N
두 번째 행, N개의 정수 A1, A2,......,AN
[출력 형식]
최소 수정된 숫자를 나타내는 정수 1개
[샘플 입력]
3
1 3 2
[샘플 출력]
1
[데이터 범위]
50% 데이터의 경우 N≤10^3
100% 데이터의 경우 1≤N≤10^5,1≤Ai≤10^9
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JAVA에서 IP와 정수를 상호 변환하는 방법본고는 JAVA에서 IP와 정수가 서로 전환되는 방법을 실례로 다루고 있다.여러분에게 참고할 수 있도록 나누어 드리겠습니다.구체적인 분석은 다음과 같다. 1. 기본 지식 포인트 IP – > 정수: IP 주소를 바이트...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.