여름방학-역동적계획 III-(A - Constructing Roads In JGShining's Kingdom)

1429 단어 동적 기획
/*
  : 2n   ,   n      ,n      ,               ,
                 ,             ,     ,
              ,                      ,
                            ,            ,
             ,                      
  :                ,                  LIS    
  :      (2 for  )   ,   n*logn     。
        (                 )
*/
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN=500005;
struct Node
{
	int p,c;
};
Node city[MAXN];
int dp[MAXN];
bool cmp(Node a,Node b)// p      
{
	return a.p<b.p;
}
int main()
{
	int n,ans=0;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&city[i].p,&city[i].c);
		}
		sort(city,city+n,cmp);// p      。
		int top=0;//LIS  
		dp[0]=0;//   
		for(int i=0;i<n;i++)
		{
			if(city[i].c>dp[top])//            LIS
			{
				dp[++top]=city[i].c;
			}
			else//         city[i].c     ,   
			{
				int l=0,r=top,mid;
				while(l<=r)
				{
					mid=(l+r)/2;
					if(city[i].c>=dp[mid])
					{
						l=mid+1;
					}
					else
					{
						r=mid-1;
					}
				}
				dp[l]=city[i].c;
			}
		}
		if(top==1)//        。
		{
			printf("Case %d:
My king, at most %d road can be built.

",++ans,top); } else { printf("Case %d:
My king, at most %d roads can be built.

",++ans,top); } } return 0; }

좋은 웹페이지 즐겨찾기