首页 > 代码库 > codeforces340D - Bubble Sort Graph dp + 最长上升子序列

codeforces340D - Bubble Sort Graph dp + 最长上升子序列

2024-07-15 13:34:34   220人阅读

题意：给你长为n的序列 ，每个节点都和在它前面且值比他大的点产生一条边，问你一个最大 两两点没有边的集合的 集合元素有多少

解题思路：想了半天才发现是最长上升子序列。。

解题代码：

 1 // File Name: 340d.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月03日 星期日 12时31分24秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 #define maxn 10000526 using namespace std;27 int st[100005];28 int num = 0 ; 29 int a[100005];30 int n ;31 void solve(int x)32 {33    int l =1 ,r = num;34    while(l <= r)35    {36       int m = (l + r)/2;37       if(st[m] <= x)38       {39         l = m +1; 40       }else {41         r = m - 1;42       }43    }44    if(l == num + 1)45    {46      num ++ ;47      st[num] = x; 48    }else{49      st[l] = x; 50    }51 }52 int main(){53    scanf("%d",&n);54    for(int i = 1;i <= n;i ++)55    {    56       scanf("%d",&a[i]);57       solve(a[i])  ; 58    }59    printf("%d\n",num);60    return 0;61 }
View Code

 


联系
我们