[伯俊]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])演算
  • #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/