acmicpc.net 2352,1365,12015,12738,2631,11722,3745(LIS(DP))

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

LIS를 구해주면 되는데 포트가 최대 40000개다. O(n^2)의 시간복잡도를 가지는 소스로는 시간

초과 에러가 뜨는데 lis는 최대 O(nlogn)으로 줄여줄 수 있다. 아래는 소스코드.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n,idx;
int num;
int arr[40001];
 
int main()
{
    ios::sync_with_stdio(false); 
    cin>>n;
    vector<int> vt;
    vector<int>::iterator itor;
    for(int i=0;i<n;i++)
        cin>>arr[i];
    vt.push_back(0);
     
    for(int i=0;i<n;i++)
    {
        num = arr[i];
        if(vt[idx] < num)
        {
            vt.push_back(num);
            idx++;
        }
        else
        {
            itor = lower_bound(vt.begin(), vt.end(), num);
            *itor = num;
        }
    }
    cout<<vt.size()-1<<'\n';
    return 0;
}

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

윗문제와 마찬가지로 O(nlogn)의 시간복잡도를 가지는 소스를 사용한다.

위 소스에서 마지막 출력부만 cout<<n-(vt.size()-1)<<'\n'; 로 바꿔주면 된다.

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

11053문제와 같지만 범위가 늘어났다. 11053을 풀었던 O(n^2)코드로는 안되고 위의 코드를 쓰면 된다.

arr만 크기를 1000001로 늘려주자.

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

12015와 같다. 근데 범위가 -10억부터다. 위의 소스코드에서 vt.push_back(0);을

vt.push_back(-1000000001); 로 바꿔주면된다.

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

위에 1365랑 똑같다.

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

가장 긴 감소하는 수열이다. 어떻게 할까? 입력받은후 -1을 곱해서 -로 만든후 가장 긴 수열을 

구하면 된다.

for(int i=0;i<n;i++)

{

   cin>>arr[i];

   arr[i]*=-1;

}

vt.push_back(-99999999);

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

맨 위의 소스에서 배열 크기 바꿔주고 eof가 나오기전까지 입력받도록 하면 된다.