21 22 131 22 33 1 Sample OutputCase 1:My king, at most 1 road can be built.Case 2:My king, at most 2 roads can be built.解题思路：题目翻译：有两个平行的直线，上面直线上的点都是富裕的村庄编号（1~n），下面直线上的点都是贫穷的村庄(1~n)，现在要修路将富裕村庄富余的资源运送到贫穷的村庄，但是修的路不能交叉，问在题目所给条件下，村庄间最多能修多少条路。题目思路很好想，就是求最长上升子序列的长度，但是题目套路太深了。。。。1. 普通动态规划做法
2. for(i = 1; i <= n; i++)
3. {
4. dp[i]=1;
5. for(j = 1; j < i; j++)
6. {
7. if(a[j]<=a[i]&&dp[j]+1>dp[i])
8. {
9. dp[i]=dp[j]+1;
10. }
11. }
12. }
13. int mmax = 1;
14. for(i = 1; i <= n; i++)
15. {
16. if(mmax < dp[i])
17. mmax = dp[i];
18. }
19. printf("%d/n",mmax);
例如一组数：
d[1..9] =2 1 5 3 6 4 8 9 7
dp[1]=1
dp[2]=1
dp[3]=2
dp[4]=2
dp[5]=3
dp[6]=3
dp[7]=4
dp[8]=5
dp[9]=4
mmax = 5,所以最长上升子序列的长度为5
该算法的时间复杂度：
当i=1时，内循环执行0次；当i=2时，内循环执行1次，当i=3时内循环执行2两次。。。。。。到i=n时，内存循环执行n-1次。总共执行0+1+2+3+…(n-1)=[n*(n-1)]/2，所以时间复杂度时O（n^2），是平方阶。对于这道题目来说，这种方法会超时。因此可以用LIS算法降低时间复杂度。LIS就是longest increasing subsquence.详细讲解请点击下面链接。
LIS详细讲解链接
看完上面的链接后就知道怎么做这个题目了，但是题目套路特别深，不仅仅是用普通动态规划的方法会超时，而且在答案输出的时候，如果最多修一条路的时候，输出的答案单词road用单数，当最多可以修的路大于1时，单词road要用复数roads。
个人做题感受：特别坑爹，套路特别深。刚做题目的时候感觉就是求最长递增子序列，感觉挺简单的，因为之前做过，结果提交一直错误，进讨论区看了一下，都说用LIS算法，就去百度LIS算法，写完之后又一直错，一直错，最后又去讨论区看了一下，发现单词还有单复数的差异。感觉错误快哭了。就感觉这个题是我见过套路最深的题目。主要还是做题太少了，看题太不认真了。
#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int lis[500005];//存放longest increasing subsequence的数组int len;struct road{ int poor; int rich;}a[500005];bool cmp(struct road r1,struct road r2){ if(r1.poor == r2.poor) return r1.rich<r2.rich; else return r1.poor<r2.poor;}int Binary_Search(int n) //二分查找，时间复杂度为对数阶{ int low,high,mid; low = 1; high = len; while(low<high) { mid = (low+high)/2; if(lis[mid]>=n) high = mid; else low = mid+1; //只让下届做改变 } return low;}int main(){ int n,i,t=0; while(~scanf("%d",&n)) { for(i = 0; i < n; i++) scanf("%d%d",&a[i].poor,&a[i].rich); sort(a,a+n,cmp); len = 0; lis[len]=0; for(i = 0; i < n; i++) { if(a[i].rich>lis[len]) { len++; lis[len]=a[i].rich; } else { int pos = Binary_Search(a[i].rich); lis[pos]=a[i].rich; } } printf("Case %d:/n",++t); if(len == 1) printf("My king, at most %d road can be built./n",len); //当道路的条数等于1时，单词road用单数 else printf("My king, at most %d roads can be built./n",len);//当道路的条数大于1时，单词road用复数 printf("/n"); } return 0;}
新闻热点
疑难解答
