[白俊]2565号電線

質問リンク:https://www.acmicpc.net/problem/2565

質問する

にゅうしゅつりょく

質問へのアクセス

dp問題は,最長増分数列を求める問題である.
A電柱は昇順に並ぶ.では、右側の電線は自分で勝手に絡んでいます.この場合、絡みを解消するには、電線を最小限に抑えるには、bの最長増分数列(LIS)だけが必要となる.

コード実装（C++）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
int cache[101];
int N;
vector<pair<int, int> > v;
int dp(int n){
    int& res = cache[n];
    if(res != -1) return res;
    res = 1;
    for(int i = n+1 ; i < N ; i++){
        if(v[n].second < v[i].second) res = max(res, dp(i)+1);
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> N;

    for(int i = 0 ; i < N ; i++){
        int temp1, temp2;
        cin >> temp1 >> temp2;
        v.push_back(make_pair(temp1,temp2));
    }    
    memset(cache,-1,sizeof(cache));
    sort(v.begin(),v.end());
    int res = 0;
    for(int i = 0 ; i < N ; i++){
        res = max(res, dp(i));
    }
    cout << N-res << "\n";
}