XDU-1107 Too Simple (DP)
1107: Too Simple
Time Limit: 2 Sec
Memory Limit: 128 MB
[ Submit][ Status][ Web Board]
Description
n개의 점의 나무, 나무의 각 점마다 두 개의 권치 x, y가 있다.x, y는 모두 정수다.이제 나무에서 가능한 한 많은 점을 골라 새 나무를 만들어야 한다. (단지 새 나무일 뿐이다.)새 나무는 만족해야 한다. 나무에 있는 임의의 두 점의 권한(xi, yi), (xj, yj)은 모두 xi
Input
여러 조의 데이터, EOF가 10조의 첫 줄 정수 n을 초과하지 않도록 처리, 2 <= n <= 100000 다음 두 줄, 각 줄 n개의 정수, 첫 줄은 n개의 점의 X 값을 표시, x1, x2, x3...xn, 공백을 분리합니다.두 번째 줄은 n개의 점의 Y 값을 나타낸다. y1, y2, y3...yn, 스페이스 바 분리.0 < x, y < 100000000
Output
출력 새 나무는 최대 몇 개의 점으로 구성될 수 있습니까?
Sample Input
5
1 5 3 2 4
8 6 9 3 4
Sample Output
3갑자기 3개월 전에 A가 빠지지 않은 문제가 몇 개 더 있었다는 생각이 들었으니 강박증인 나는 틀림없이 참을 수 없을 것이다.
첫 번째 반응은 O(n^2)의 알고리즘이다. 정렬(x승차순, y승차순) 후 가장 긴 상승자 서열을 구하고TLE는 이 방법을 과감하게 포기한다.
또 정렬 후 기본적으로 1차원의 최장 상승자 서열과 유사하다는 것을 생각하고 O(nlogn)의 최장 상승자 서열 알고리즘을 찾아 배웠다.WA야, 그리고 욕심내서 x중복된 점을 지웠어. 미친 WA는 십여 발이야. 이분 조건인 줄 알았어. 비벼버렸어...침대에 누운 지 얼마 되지 않아 욕심 의 반례 를 생각해 내어, 다음날 로 미룰 수밖에 없었다
아침에 일어나서 흥분해서 욕심을 없애고 계속해서 WA 10여 발을 이어서 또 이분 조건인 줄 알고 비볐다.
끊임없는 디버깅에서, 이렇게 정렬하면, 어떤 경우에는 가장 긴 길이를 줄일 수 있다는 것을 발견했다.
예를 들면 다음과 같습니다.
3
1 4 4
2 1 3
이 데이터 세트는
(4,1)까지 진행할 때 (4,1)과 (1,2)에서 y값이 1<2로 가장 긴 상승자 서열에서 첫 번째 점의 최소값이 (1,2)에서 (4,1)로 바뀌어 (4,3)의 최대 길이를 업데이트할 수 없습니다.
처음에는 정렬 방법을 바꿀 생각을 하지 못했는데, 단지 다른 수조를 추가했고, x와 같은 점은 Y값에 따라 순서를 낮추어 훑어보았다.
AC 이후 x 오름차순을 직접 누르고 y 오름차순으로 정렬할 수 있다고 생각했을 때 가장 긴 오름차순을 구할 때 아래 표시를 누르기만 하면 된다.
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node {
int x,y;
bool operator < (const Node& a) const {
return x<a.x||(x==a.x&&y>a.y);// x ， y
}
}a[100005];
int mn[100005],n;
int LIS() {
int ans=0,i,l,r,mid;
for(i=1;i<=n;++i) {
l=1,r=ans;
while(l<=r) {// y a[i].y
mid=(l+r)>>1;
if(a[mn[mid]].y<a[i].y)
l=mid+1;
else
r=mid-1;
}
if(l>ans)// y a[i].y ，
mn[ans=l]=i;
else if(a[mn[l]].y>a[i].y)
mn[l]=i;
}
return ans;
}
int main() {
int i;
while(scanf("%d",&n)==1) {
for(i=1;i<=n;++i)
scanf("%d",&a[i].x);
for(i=1;i<=n;++i)
scanf("%d",&a[i].y);
sort(a+1,a+n+1);
printf("%d
",LIS());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
