本文主要是介绍DP.單調隊列::poj1631 Bridging signals,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目大意:两岸的同等数目的信号灯一一对应,连线,从中找出最多的线出来,它们之间互不交叉。只要求输出最大的线条数。
本题不需要画图了,因为画了图会尝试用二维的DP去做,吃力不讨好,既然输入是一维的一个串,而且该串简洁地包含了全部的信息,那么直接DP何乐而不为呢?
通过对例子(4,2,6,3,1,5)的观察,发现被选中的数字是递增的!再找了一组例子观察,发现同样的规律。那么问题转化为求序列的最长递增子序列。
状态的表述和Poj-1050“to the max”的状态描述有异曲同工之妙,这里用f[i]表示a[1..i]中以i结尾最长递增子序列的长度。那么状态方程为:
f[i]=max{1,f[j]+1 | j<i && a[j]<a[i]} // 初始化为for i=1..p:f[i]=0
用两个for扫描即可,最后求最大的f[i]就行。时间代价为O(n^2).
比较了Poj-1050“to the max”,总觉得还可以再好。用单调队列的思想?是否可以Greedy?考察(1,3,7,4,6),前面的(1,3,7)没甚好说,关键是如何处理 4 ,因为(1,3,4)也是可以的而且似乎比(1,3,7)的要更好,因为后面的 6 在前者容得下而在后者容不下。也就是说,(1,3,4)的效用比(1,3,7)的要大,但这一过程又不影响当前的“最长”,这就Greedy了!由于替换需要查找,这里自然地选用二分查找,详见http://blog.csdn.net/timoss/article/details/6693127。时间代价为O(nlgn),这里的lgn部分是在查找中省下来的,若不省的话通过Greedy也能把常数因子降下来。
下面的代码一次就AC,Memory:384k;Time:422ms
#include "stdafx.h"
#include <iostream>
using namespace std;
unsigned int n,p,a[40000];
void bisearch(int top,int temp) //二分查找替換元素
{
int low=1,high=top,m;
int find=0;
while(low<=high && !find){
m=(low+high)/2;
if(temp<a[m]){
if(temp>a[m-1]){ a[m]=temp;find=1;}
else high=m-1;
}
else{
if(temp<a[m+1]){ a[m+1]=temp;find=1;}
else low=m+1;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
cin>>n;
while(n>0){
cin>>p;
int temp,top=0;
a[0]=0;
while(p>0){
cin>>temp;
if(temp>a[top]) a[++top]=temp;
else bisearch(top,temp);
p--;
}
cout<<top<<endl;
n--;
}
return 0;
}
总结:本题挺有趣的,问题本身就是有趣的。关于维数的思考是值得的,因为我在二维的错综复杂的图中纠结了不少时间。解决本题的关键在于有一个好的“观察”,然后就是问题的化归以及归约问题的求解。“求序列的最长递增子序列”这应该是一个基本的问题了,也是这个问题的本质所在。DP方法没什么好讲的,关键是状态表述的好坏而已。值得我们思考的是有没有更好的?本题和单调队列似有某种一衣带水的关系,所以用队列去解决本问题是自然的,但它和单调队列又有很本质的区别:后者是只和当前元素下标有关,而前者是在控制不变量的情况之下尽量最优。前者是建立在对DP过程状态的深入观察之上的。说到底,还是要有一个好的观察,以及类比的方法。上面代码很简单,其中很大一块是对二分查找代码的改写。
ps:上面的二分查找可以寫成一個函數,這樣代碼比較美觀。
这篇关于DP.單調隊列::poj1631 Bridging signals的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!