题意:有贫困和富有的地方,每个地方只能连接一个地方,不能有交叉,给你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