网站怎么做可以被收录,怎么仿网站,网站友情链接怎么样做,企业咨询公司经营范围点我看题目 题意 #xff1a;两条平行线上分别有两种城市的生存#xff0c;一条线上是贫穷城市#xff0c;他们每一座城市都刚好只缺乏一种物资#xff0c;而另一条线上是富有城市#xff0c;他们每一座城市刚好只富有一种物资#xff0c;所以要从富有城市出口到贫穷城市…点我看题目 题意 两条平行线上分别有两种城市的生存一条线上是贫穷城市他们每一座城市都刚好只缺乏一种物资而另一条线上是富有城市他们每一座城市刚好只富有一种物资所以要从富有城市出口到贫穷城市所以要修路但是不能从富有的修到富有的也不能从贫穷的修到贫穷的只能从富有的修到贫穷的但是不允许修交叉路所以问你最多能修多少条路。 题意 这个题一开始我瞅了好久都没觉得是DP后来二师兄给讲了一下才恍然大悟。其实就是用到了DP中的那个最长上升子序列把题中贫穷城市的坐标当成数组的下标跟其相连的富有城市的坐标当作数组的值这样的话因为不能有交叉所以只能一直往右这就好比找最长上升子序列因为用朴素的算法会超时所以要用二分。 解题报告这里边的解释非常详细就是怎么用二分去做其实就是将找到的子序列保存到B数组里但是往里插入的过程用的是二分。 //HDU 1025#include iostream
#include stdio.h
#include string.husing namespace std;int dp[505000] ;
int B[505000] ;int main()
{int n ;int casee 1 ;while(~scanf(%d,n)){int a,b ;for(int i 0 ; i n ; i){scanf(%d %d,a,b) ;dp[a] b ;//这样就相当于去找dp这个数组的最长上升子序列了}int len 1 ;B[1] dp[1] ;for(int i 2 ; i n ; i)//这里掉了等号WA到死啊{int low 1 , high len ;while(low high){int mid (lowhigh) 1 ;if(B[mid] dp[i]) low mid1 ;else high mid - 1 ;}B[low] dp[i] ;if(low len) len ;}printf(Case %d:\n,casee) ;if(len 1)printf(My king, at most 1 road can be built.\n\n) ;else printf(My king, at most %d roads can be built.\n\n,len) ;}return 0;
} View Code 转载于:https://www.cnblogs.com/luyingfeng/p/3569595.html
