[伯俊]2550電球
白駿2550電球 https://www.acmicpc.net/problem/2550 スイッチの接続線の重複を避けるために、右側の接続スイッチの位置は増分数列 であるべきである.左スイッチの番号->sw 1[i]に格納
右側のスイッチに格納されている番号->sw 2[i]
sw 1[i]とsw 2[i]を接続する場合、スイッチが右側に接続されている場所
->line[i]に保存されている line[i]のLISアレイを求める時
->レコード配列の一番後ろからナビゲート
->レコード[i]に格納されているインデックスは、順番に降順に並べられます.
->retベクトルのpush back(sw 2[line[i])演算 電球の解読
https://fbdp1202.github.io/BOJ/2019/06/11/BOJ_2550/
右側のスイッチに格納されている番号->sw 2[i]
sw 1[i]とsw 2[i]を接続する場合、スイッチが右側に接続されている場所
->line[i]に保存されている
->レコード配列の一番後ろからナビゲート
->レコード[i]に格納されているインデックスは、順番に降順に並べられます.
->retベクトルのpush back(sw 2[line[i])演算
#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 sw1[10000] = { 0 };
int sw2[10000] = { 0 };
int line[10000] = { 0 };
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> sw1[i];
for (int i = 0; i < n; i++) cin >> sw2[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (sw1[i] == sw2[j])
line[i] = j;
vector <int> vt;
vector <int> record;
vector <int> ret;
// record 벡터에 line[i]가 vt벡터에 저장되는 위치 저장
int idx = 0;
vt.push_back(line[0]);
record.push_back(0);
for (int i = 1; i < n; i++) {
if (vt.back() < line[i]) {
vt.push_back(line[i]);
record.push_back(++idx);
}
else {
auto it = lower_bound(vt.begin(), vt.end(), line[i]);
*it = line[i];
record.push_back(it - vt.begin());
}
}
// lis 추적
int flag = idx;
for (int i = n - 1; i >= 0; i--) {
if (record[i] == flag) {
ret.push_back(sw2[line[i]]);
flag--;
}
if (flag == -1)
break;
}
sort(ret.begin(), ret.end());
//결과
cout <<idx + 1<< "\n";
for (auto it = ret.begin(); it != ret.end(); it++)
cout << *it << " ";
return 0;
}
📌参考資料https://fbdp1202.github.io/BOJ/2019/06/11/BOJ_2550/
Reference
この問題について([伯俊]2550電球), 我々は、より多くの情報をここで見つけました https://velog.io/@sunjoo9912/백준-2550-전구テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol