nyoj-14 회의장 안배 문제[dp]

2010 단어 dp

회의장 안배 문제


시간 제한:
3000ms | 메모리 제한:
65535 KB
난이도:
4
묘사
학교의 작은 강당은 매일 많은 행사가 있는데 시간이 있으면 이런 행사의 계획 시간과 충돌이 발생하기 때문에 일부 행사를 선택하여 개최해야 한다.샤오류의 업무는 학교 소강당의 활동을 안배하는 것이다. 시간당 최대 한 개의 활동을 안배하는 것이다.현재 샤오유는 활동 계획의 시간표가 몇 개 있다. 그는 가능한 한 더 많은 활동을 안배하고 싶은데 어떻게 안배해야 할지 물어보자.
입력
첫 번째 줄은 정형수 m(m<100)로 모두 m조 테스트 데이터가 있음을 나타낸다.
각 그룹의 테스트 데이터의 첫 줄은 하나의 정수 n(1다음 n행에는 두 개의 양의 정수 Bi, Ei(0<=Bi, Ei<10000)가 있으며 각각 i번째 활동의 시작과 끝 시간(Bi<=Ei)을 나타냅니다.
출력
각 그룹의 입력에 대해 최대 배정할 수 있는 활동 수량을 출력합니다.
그룹당 출력이 한 줄 차지
샘플 입력
2
2
1 10
10 11
3
1 10
10 11
11 20

샘플 출력
1
2

프롬프트
주의: 이전 이벤트가 t시간에 끝나면 다음 이벤트는 t+1시간에 시작해야 합니다
질문
우선 활동 시간의 시작점을 정렬한다.dp[i]는 0~i 이 활동들이 구성할 수 있는 최대 활동 수를 나타낸다.dp[i]=Max(dp[j]+1,dp[i]);j 활동 시간과 i가 충돌하지 않을 때.dp[i]=Max(dp[j],dp[i]);j 활동 시간과 i가 충돌할 때
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Maxsize 11000
int n;
struct time{
	int b,e;
}v[Maxsize];
int dp[Maxsize];
int com(const void *a,const void *b)
{
	time *c=(time *)a;
	time *d=(time *)b;
	/*if(c->b!=d->b)
		
	else return c->e-d->e;*/
	return c->b-d->b;
}
int findmax(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int m;
	int i,j;
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d%d",&v[i].b,&v[i].e);
		qsort(v,n,sizeof(v[0]),com);
		for(i=0;i<n;i++)
			dp[i]=1;
		int ans=dp[0];
		for(i=1;i<n;i++)
		{
			for(j=i-1;j>=0;j--)
			{
				if(v[j].e<v[i].b)
				{
					dp[i]=findmax(dp[i],dp[j]+1);
					break;
				}
				else dp[i]=findmax(dp[i],dp[j]);
			}
			ans=findmax(dp[i],ans);
		}
		printf("%d
",ans);
	}
	return 0;
}
React의 양식 이벤트
[문제풀이] CF1107 E: Vasya and Binary String

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage