首页 > 代码库 > poj 1631 Bridging signals
poj 1631 Bridging signals
题目大意：如何留下最多的桥使其不相交
这个题看起来很麻烦，读懂了之后其实是让你求最长上升子序列
用动态规划求解
dp[i]表示长度为i的上升子序列的第i个元素的最小值
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 using namespace std; 5 6 int dp[40002]; 7 int n; 8 9 int main(int argc, char const *argv[])10 {11 int t;12 freopen("input.txt","r",stdin);13 scanf("%d",&t);14 while(t--) {15 scanf("%d",&n);16 int cnt = 0;17 while(n--) {18 int tmp;19 scanf("%d",&tmp);20 if(cnt == 0 || tmp > dp[cnt]) {21 cnt++;22 dp[cnt] = tmp;23 }24 else {25 int p = lower_bound(dp, dp+cnt+1, tmp) - dp;26 dp[p] = tmp;27 }28 }29 printf("%d\n",cnt);30 } 31 return 0;32 }
另外,lower_bound()为二分搜索的库函数，返回不小于tmp的指针
poj 1631 Bridging signals
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。