[DP] 합창 대형

8963 단어 DP

제목 설명


N명의 학우들이 한 줄로 서 있는데 음악 선생님은 그 중의 (N-K) 학우들을 나와서 나머지 K명의 학우들을 합창 대형으로 만들어야 한다.합창대형은 이런 대형을 가리킨다. K명의 학우를 왼쪽에서 오른쪽으로 순서대로 번호가 1, 2..., K로 설정하면 그들의 키가 각각 T1, T2,..., TK로 설정하면 그들의 키는 T1을 만족시킨다...>TK(1<=i<=K).너의 임무는 모든 N명의 학우들의 키를 알고 있기 때문에 최소한 몇 명의 학우들이 줄을 서서 나머지 학우들을 합창 대형으로 배열할 수 있도록 계산하는 것이다.

입력


입력한 첫 번째 줄은 전체 학우의 총수를 나타내는 정수 N(2<=N<=100)이다.두 번째 줄에는 n개의 정수가 있고 빈칸으로 구분되며 i번째 정수인 Ti(130<=Ti<=230)는 i번째 학생의 키(센티미터)다.

출력


출력은 한 줄을 포함하고 이 줄은 하나의 정수만 포함하며 적어도 몇 명의 학우가 줄을 서야 한다.
샘플 가져오기
8
186 186 150 200 160 130 197 220

출력 예제
4

사고의 방향


먼저 앞에서 뒤로 a[i]보다 작은 개수를 f[1][]수조, 리와 뒤에서 앞으로 a[i]보다 작은 개수를 f[2][]수조에 저장한 다음에 어떤 사람을 매거하여 그를 중점으로 하고 몇 명을 조정해야 하는지 판단하고 마지막에 어느 사람이 가장 작은지 판단한다.
#include
#include
using namespace std;
int n,a[105],f[3][105],ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i;j++)
			if(a[i]>a[j])f[1][i]=max(f[1][i],f[1][j]+1);//       a[i]  
	for(int i=n;i>=1;i--)
		for(int j=n+1;j>=i;j--)
			if(a[i]>a[j])f[2][i]=max(f[2][i],f[2][j]+1);//       a[i]  
	for(int i=1;i<=n;i++)
		ans=max(f[1][i]+f[2][i]-1,ans);//  a[i]       
	printf("%d",n-ans);//       
	return 0;
}
이온 스켈레톤 로더
상태 압축

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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