시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 720 | 224 | 195 | 33.679% |
어떠한 다이아몬드의 가치는 그 다이아몬드의 중량인 캐럿과 선명도에 의해서 결정됩니다. 즉, 작지만 선명한 다이아몬드가 크고 선명하지 않은 다이아몬드보다는 가치가 높습니다. 다이아몬드의 선명도는 0.0-10.0의 스캐일로 표현할 수 있는데, 0.0의 선명도는 완벽하게 선명한 다이아몬드를 나타내고 10.0은 가장 결함이 많은 다이아몬드를 나타냅니다.
N개의 다이아몬드의 중량 wi와 선명도 ci의 정보가 주어졌을때, 이 중에서 다이아몬드의 중량이 높아지고, 선명도 값이 낮아지는 부분열 중 최장의 것의 길이를 구하세요. 예를들어 주어진 정보가 다음과 같다면
wi | ci |
1.5 | 9.0 |
2.0 | 2.0 |
2.5 | 6.0 |
3.0 | 5.0 |
4.0 | 2.0 |
10.0 | 5.5 |
다이아몬드 중량이 높아지고, 선명도 값이 낮아지는 부분열 중 길이가 최장인 것은 다음과 같습니다.
1.5 | 9.0 |
2.5 | 6.0 |
3.0 | 5.0 |
4.0 | 2.0 |
왜냐하면 표에 나와있는 부분열을 보면, 무게는 증가하고, 선명도의 값은 감소하기 때문입니다.
테스트 케이스의 개수 T가 주어지고 (1≤T≤100) 각 테스트 케이스마다 다이아몬드의 정보의 개수 N (1≤N≤200)이 주어집니다. 그리고 N개의 줄에 걸쳐서 다이아몬드의 무게와 선명도 wi, ci가 주어집니다 (0≤wi,ci≤100).
각 테스트 케이스마다 다이아몬드의 가치가 높아지는 부분열중 최장의 것의 길이를 구하세요.
3 2 1.0 1.0 1.5 0.0 3 1.0 1.0 1.0 1.0 1.0 1.0 6 1.5 9.0 2.0 2.0 2.5 6.0 3.0 5.0 4.0 2.0 10.0 5.5
2 1 4
ICPC > Regionals > North America > Pacific Northwest Regional > 2014 Pacific Northwest Region Programming Contest > Division 2 O번