/*转载请注明出处:乄心-小黄豆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; else j=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; else cout<<"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; else cout<<"Case "<<count++<<":\n"<<"My king, at most "<<LIS(City,n)<<" roads can be built."<<endl<<endl; } return 0; }