本文主要是介绍HDU-1025 裸最长递增子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
河两岸各有n个城市 每个城市可以向对岸建路 建的路不能交叉
问最多可以建多少条路
思路：
可以把模型转化为最长递增子序列
河的一岸作为序列的下标 另一岸作为序列的值
不相交既为 城市i前面的城市不能建比城市i连接的城市后
由于数据比较大 n<500000 n^2版 果断爆 只能用 nlogn 版
坑：
深坑... 输出要分单复数 只能建一条路的时候要输出road而复数要输出roads ..... 不看讨论区 坑到死都不知道怎么死的 = = ！
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = 500005;
int n;
int p[maxn],dp[maxn];int main()
{//freopen("data.in","r",stdin);int c,d,cas = 1;while( scanf("%d",&n) != EOF ){for( int i = 1; i <= n; i ++ ){scanf("%d%d",&c,&d);p[c] = d;}dp[0] = -1;int top = 0;for( int i = 1; i <= n; i ++ ){if( p[i] > dp[top] )dp[++top] = p[i];else{int ld = 1,rd = top,mid;while( ld <= rd ){mid = ( ld + rd )/2;if( p[i] > dp[mid] )ld = mid + 1;elserd = mid - 1;}dp[ld] = p[i];}}if( top == 1 )printf("Case %d:\nMy king, at most 1 road can be built.\n",cas++);elseprintf("Case %d:\nMy king, at most %d roads can be built.\n",cas++,top);puts("");}return 0;
}
这篇关于HDU-1025 裸最长递增子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
