hdu 1257 최소 차단 시스템 dp

909 단어
간단한 dp, 모든 시스템의 미사일을 현재의 최저 고도로 보존하기만 하면, 이후의 미사일은 모두 최소치로 그보다 큰 시스템 중 최소치를 사용하게 된다.
OK.매번 원래 시스템의 최저 높이를 갱신하거나 새 시스템을 추가하거나...
코드:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<algorithm>

using namespace std;
int cmp(const void *a,const void *b)
{
	return *(int *)a - *(int *)b;
}
int main()
{
	int n,len,i,j;
	int a[100005];
	int b[100005];
	while(cin >> n)
	{
		len = 0;
		for(i=1; i<=n ;i++)
		{
			cin >> a[i];
			int flag = 0;
			for(j=1; j<=len; j++)
			{
				if(a[i] <= b[j])
				{
					b[j] = a[i];
					flag = 1;
					break;
				}
			}
			if(!flag)
			{
				len++;
				b[len] = a[i];
				qsort(b+1,len,sizeof(b[0]),cmp);
			}
		}
		cout << len << endl;
	}
	return 0;
}

좋은 웹페이지 즐겨찾기