[伯俊]1365ねじれ電線
白駿1365ねじれ電線 https://www.acmicpc.net/problem/1365 番の左側の電柱と右側の電柱を結ぶ電線が絞首刑にならないように、右側の電柱の位置は増加した数列でなければならない.
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
int lis = 0;
vector <int> vt;
vt.push_back(INT_MIN);
for (int i = 0; i < n; i++) {
int A;
cin >> A;
if (vt.back() < A) {
vt.push_back(A);
lis++;
}
else {
auto it = lower_bound(vt.begin(), vt.end(), A);
*it = A;
}
}
cout << n - lis;
return 0;
} Reference
この問題について([伯俊]1365ねじれ電線), 我々は、より多くの情報をここで見つけました https://velog.io/@sunjoo9912/백준-1365-꼬인-전깃줄テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol