首页 > 其他 > 详细

HDU - 1025 Constructing Roads In JGShining's Kingdom

时间:2014-03-15 19:40:19      阅读:634      评论:0      收藏:0      [点我收藏+]

题意:有贫困和富有的地方,每个地方只能连接一个地方,不能有交叉,给你n条线,求最多的连接条数

思路:LIS的应用,尽量的往前连

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 500010;

int n,len,t;
int a[MAXN],dp[MAXN];

void DP(){
	dp[1] = a[1];
	len = 1;
	for (int i = 2; i <= n; i++){
		int l = 1,r = len;
		while (l <= r){
			int m = (l+r) >> 1;
			if (dp[m] < a[i]) //找到第一个大于等于a[i]的数
				l = m + 1;
			else r = m-1;
		}
		dp[l] = a[i];
		if (l > len)
			len++;
	}
	printf("Case %d:\n",t++);
	if (len == 1)
		printf("My king, at most 1 road can be built.\n");
	else printf("My king, at most %d roads can be built.\n",len);
	printf("\n");
}

int main(){
	t = 1;	
	while (scanf("%d",&n) != EOF){
		for (int i = 1; i <= n; i++){
			int x,y;
			scanf("%d%d",&x,&y);
			a[x] = y;
		}
		DP();
	}
	return 0;
}



HDU - 1025 Constructing Roads In JGShining's Kingdom,布布扣,bubuko.com

HDU - 1025 Constructing Roads In JGShining's Kingdom

原文:http://blog.csdn.net/u011345136/article/details/21294657

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!