本文主要是介绍HDU-1025-动规-最长上升子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*转载请注明出处：乄心-小黄豆http://blog.csdn.net/wuxinxiaohuangdou*/
题目大意：贫穷城市去富裕城市 进口资源要建公路，但不允许交叉，求最多能建几条公路？
Input: n行,每行p（贫穷城市）r（富裕城市）。
Output: 最多建几天公路？按格式输出。
转化一下，容易看出是求 最长上升子序列(LIS).
第一种方法：/*140MS 4304K AC 最长上升子序列O(nlogn)二分算法*/
算法精髓：维护一个一维数组！
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 500010
int City[MAX];
int count=1;
int bsearch(int *c,int n,int a) //二分找更具潜力的值!
{ /*找到了则表示比起原先值，现在的值将能够得到更长的升序子序列，因为现在的值更小，向序列尾走的更远些！*/int j=0;int l=1,r=n;while(l<=r){int mid=(l+r)>>1; if(c[mid]<a&&a<=c[mid+1]){j=mid+1;break;}else if(a<c[mid]){j=mid; //j一定要保存一下这时的值！因为你需要的不一定满足第一个if语句！r=mid-1;}else l=mid+1;}return j;
}
int LIS(int *a,int n)
{int i,j,size=1;int *c=new int[n+1];//键值表示子序列长度，映射表示这个长度下的子序列最小尾数int *dp=new int[n+1];c[1]=a[1];dp[1]=1;for(i=2;i<=n;i++){if(a[i]>=c[size]) //如果比此时 最大的升序子序列长度 所对应的最小值 大的话 ，直接把长度加1.j=++size;elsej=bsearch(c,size,a[i]); //否则 去寻找能够用a[i]来更新的 最小尾数！ c[j]=a[i];dp[i]=j;}return size;
}
int main()
{int n;while(~scanf("%d",&n)){int p,r;for(int i=1;i<=n;i++){scanf("%d%d",&p,&r);City[p]=r;}if(LIS(City,n)==1)cout<<"Case "<<count++<<":\n"<<"My king, at most 1 road can be built."<<endl<<endl;elsecout<<"Case "<<count++<<":\n"<<"My king, at most "<<LIS(City,n)<<" roads can be built."<<endl<<endl;}return 0;
}
第二种方法：以下是LIS的 O(n^2)的做法. 超时！！
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 500010
int City[MAX];
int count=1;
int LIS(int *a,int n)
{int i,j,m=0,ans=1;int *dp=new int[n+1];dp[1]=1;for(i=2;i<=n;i++) // 从序列头枚举到尾！{m=0;for(j=1;j<i;j++) //枚举此时位置之前的子序列 的各个dp值即（升序子序列长度）{if(dp[j]>m&&a[j]<a[i]) m=dp[j];}dp[i]=m+1; //得到i位置的dp值!if(ans<dp[i])ans=dp[i];}return ans;
}
using namespace std;
int main()
{int n;while(~scanf("%d",&n)){int p,r;for(int i=1;i<=n;i++){scanf("%d%d",&p,&r);City[p]=r;}if(LIS(City,n)==1)cout<<"Case "<<count++<<":\n"<<"My king, at most 1 road can be built."<<endl<<endl;elsecout<<"Case "<<count++<<":\n"<<"My king, at most "<<LIS(City,n)<<" roads can be built."<<endl<<endl;}return 0;
}
这篇关于HDU-1025-动规-最长上升子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
