Bridging signals POJ - 1631

本文主要是介绍Bridging signals POJ - 1631，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意是给你n组数据，每组pi个数据，分别求出每组的最大不下降自序列的长度

动态规划，dp[i]是长度为i时结尾的最小字符，这种DP方式能够利用二分搜索找到每个字符在dp数组的位置，节省时间

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <fstream>
const int MAX = 1e5+10;
const int INF = 1e6;using namespace std;//测试函数 
int main(){ifstream cin ("D:\\钢铁程序员\\程序数据\\056桥接信号.txt");//从文件读取数据流，省去手动输入的麻烦 if(!cin){//读取如果失败 cout << "ERROR" << endl;}int n, p;int a[MAX];int dp[MAX];//存放长度为 i 时的最小字符 cin >> n;while(n--){cin >> p;for(int i=0; i<p; i++)cin >> a[i];//更新规则 要大于前边，小于当前值 fill(dp, dp+p, INF);dp[0] = a[0];for(int i=0; i<p; i++)*lower_bound(dp, dp+p, a[i]) = a[i];int ans;ans = lower_bound(dp, dp+p, INF) - dp;cout << ans << endl;}cin.close();//打开文件以后要关闭 return 0;
} 

 

这篇关于Bridging signals POJ - 1631的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---