这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1025
题意:河两岸各有n各点,编号从左到右都依次为1~n, 已知它们与对岸某点能先连,若不能相交,最多能连几点。
仔细分析题目,可以联系到LIS。
因为数据量较大,所以用LIS的Nlog(N)的方法做。
LIS算法详细讲解见:http://www.wutianqi.com/?p=1850
#include
using namespace std;
int p[500005], b[500005];
int n;
int bSearch(int num, int k)
{
int low=1, high=k;
while(low<=high)
{
int mid=(low+high)/2;
if(num>=b[mid])
low=mid+1;
else
high=mid-1;
}
return low;
}
int LIS()
{
int low = 1, high = n;
int k = 1;
b[1] = p[1];
for(int i=2; i<=n; ++i)
{
if(p[i]>=b[k])
b[++k] = p[i];
else
{
int pos = bSearch(p[i], k);
b[pos] = p[i];
}
}
return k;
}
int main()
{
int a, b;
int nCases = 1;
while(scanf("%d", &n;) != EOF)
{
for(int i=1; i<=n; ++i)
{
scanf("%d %d", &a;, &b;);
p[a] = b;
}
int ans = LIS();
printf("Case %d:\nMy king, at most %d road", nCases++, ans);
if(ans != 1) printf("s");
printf(" can be built.\n\n");
}
return 0;
}