acmicpc.net 11503,11568,1965(LIS(DP)), 2565(LIS(DP))

https://www.acmicpc.net/problem/11053

https://www.acmicpc.net/problem/11568

https://www.acmicpc.net/problem/1965

기본적인 LIS문제. 세개다 똑같은 소스로 해결된다. O(n^2)의 시간복잡도

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n;
int cache[1001], S[1001];

int lis(int start) {
	int& ret = cache[start+1];
	if(ret != -1) return ret;
	ret = 1;
	for(int next = start+1; next < n; ++next)
		if(S[start] < S[next])
			ret = max(ret, lis(next) + 1);
	return ret;
}

int main() 
{
    cin >> n;
    for(int i=0;i<n;i++) 
		cin>>S[i];
	for(int i=0;i<1001;i++)
		cache[i] = -1;
    cout << lis(-1)-1 << endl;
}

https://www.acmicpc.net/problem/2565

좀 변형된 문제. A를 기준으로 정렬한 후 B로 가는 전깃줄을 LIS로 처리하면 된다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int a,b,n;
int cache[1001], arr[1001];
vector<pair<int, int>> S;

int lis(int start) {
	int& ret = cache[start+1];
	if(ret != -1) return ret;
	ret = 1;
	for(int next = start+1; next < n; ++next)
		if(arr[start] < arr[next])
			ret = max(ret, lis(next) + 1);
	return ret;
}

int main() 
{
    cin>>n;
    for(int i=0;i<n;i++) 
	{
		cin>>a>>b;
		S.push_back(make_pair(a,b));
	}
	sort(S.begin(), S.end());
	for(int i=0;i<1001;i++)
		cache[i] = -1;
	for(int i=0;i<S.size();i++)
		arr[i] = S[i].second;
    cout << n-(lis(-1)-1) << endl;
}