HDU 1025 (最长上升子序列(nlogn)算法)

ゝ一世哀愁。 2024-02-17 19:22 81阅读 0赞

![尴尬][awkward.gif]本题真是各种WR都遇到了。 。哎。不负苦心人

题意：给一个n代表两边城市的个数，两边都有n个城市，城市编号不会重复，要求找最多能修多少路（路不能交叉）

思路：就是找最长上升子序列（用复杂度nlogn的方法做）

AC代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=5e5+10;
    int t[maxn];
    int v[maxn];
    int n;
    int len;
    int binary_seacher(int i){
    	int left=1,right=len;
    	while(left<=right){   //不要忘记了这里的等号 
    		int mid=(left+right)/2;
    		if(v[i]>t[mid])
    		  left=mid+1;
    		else 
    		   right=mid-1;
    	}
    	return left;
    }
    int main(){
    	int count1=0;
    	while(scanf("%d",&n)==1){
    		memset(v,0,sizeof(v));
    		memset(t,0,sizeof(t));
    		for(int i=0;i<n;i++){
    			int p,r;
    			scanf("%d%d",&p,&r);
    			v[p]=r;
    		}
    	    t[1]=v[1];
            len=1;
    		for(int i=2;i<=n;i++){
    			if(v[i])
    			 if(v[i]>t[len])
    			   t[++len]=v[i];
    			 else{
    				int k=binary_seacher(i);
    				t[k]=v[i];
    			}
    		}
    		printf("Case %d:\n",++count1);
    		if(len==1)printf("My king, at most %d road can be built.\n\n",len);
    		else printf("My king, at most %d roads can be built.\n\n",len);
    	}
    	return 0;
    }

[awkward.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/75a6d345d0f6478bba095fb8141340f9.png

发表评论取消回复

表情：

评论列表（有 0 条评论，81人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1950 Bridging signals (最长递增子序列（nlogn算法）

题意：题目不怎么好读，好多生僻单词，和图一对比就清楚了，就是端口对接，在连线不交叉的情况下，最多连线条数。思路：最长递增子序列（nlogn算法），和hdu1025思路一样。

偏执的太偏执、/ 2024年02月17日 19:22/ 0 赞/ 74 阅读

相关 HDU 1025 (最长上升子序列(nlogn)算法)

![尴尬][awkward.gif]本题真是各种WR都遇到了。。哎。不负苦心人题意：给一个n代表两边城市的个数，两边都有n个城市，城市编号不会重复，要求找最多能修多少路（

ゝ一世哀愁。/ 2024年02月17日 19:22/ 0 赞/ 82 阅读

相关最长上升子序列

最长上升子序列 1、参考资料 https://leetcode-cn.com/problems/longest-increasing-subsequence/ h

- 日理万妓/ 2022年12月04日 07:57/ 0 赞/ 250 阅读

相关最长不上升子序列的优化（nlogn）

一般的DP写法： for (int i=1;i<=t;i++) { f[i]=1;

港控/mmm°/ 2022年09月30日 06:29/ 0 赞/ 148 阅读

相关最长上升子序列nlogn算法

这题目是经典的DP题目，也可叫作LIS（Longest Increasing Subsequence）最长上升子序列或者最长不下降子序列。很基础的题目，有两种算法，复杂度分

╰半橙微兮°/ 2022年08月20日 04:15/ 0 赞/ 172 阅读

相关最长上升子序列O(nlogn)

模板： include <iostream> include <cstdio> using namespace std; const

秒速五厘米/ 2022年08月17日 14:23/ 0 赞/ 141 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

港控/mmm°/ 2022年07月12日 02:47/ 0 赞/ 249 阅读

相关最长上升子序列

严格上升和非严格上升的 include <iostream> using namespace std; int main() {

柔光的暖阳◎/ 2022年06月15日 09:52/ 0 赞/ 337 阅读

相关最长上升子序列（LIS）算法

理解：该子序列中后一项都比前一项大，例如有序列2 7 1 5 6 4 3 8 9，则`最长上升子序列`为2 5 6 8 9。具体应用：用于确定一个代价最小的调整方案

本是古典何须时尚/ 2022年05月28日 01:46/ 0 赞/ 251 阅读

相关最长上升子序列 nlogn

最长上升子序列有dp的写法 f\[i\]:=max（f\[j\]）+1; f\[1\]:=1; ![ContractedBlock.gif][] ![ExpandedBl

迈不过友情╰/ 2022年01月07日 09:39/ 0 赞/ 207 阅读