[ BOJ 10571 ] 다이아몬드

http://icpc.me/10571

문제

중량은 증가하면서 선명도는 감사하는 최대의 수열을 찾아라

풀이

LIS 하듯이 하면된다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<double,double> pii;
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        int x;
        scanf("%d",&x);
        vector<pii> v;
        double l1,l2;
        for(int i=0,l;i<x;i++) scanf("%lf %lf",&l1,&l2),v.push_back({l1,l2});
        int dp[300]={0};
        for(int i=0;i<x;i++)
        {
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
                if(v[j].first < v[i].first && v[j].second > v[i].second) dp[i]=max(dp[j]+1,dp[i]);
            }
        }
        int ans=dp[0];
        for(int i=1;i<x;i++) ans=max(ans,dp[i]);
        printf("%d\n",ans);
    }
}