首页 > 代码库 > HDU 1950 Bridging signals

HDU 1950 Bridging signals

2024-07-13 16:12:51   216人阅读

那么一大篇的题目描述还真是吓人。

仔细一读其实就是一个LIS，还无任何变形。

刚刚学会了个二分优化的DP，1A无压力。

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 40000 + 10; 8 int a[maxn]; 9 int dp[maxn];10 11 int main(void)12 {13     #ifdef LOCAL14         freopen("1950in.txt", "r", stdin);15     #endif16 17     int N;18     scanf("%d", &N);19     while(N--)20     {21         int n;22         scanf("%d", &n);23         int i;24         for(i = 1; i <= n; ++i)25             scanf("%d", &a[i]);26         dp[1] = a[1];27         int len = 1;28 29         for(i = 2; i <= n; ++i)30         {31             int left = 1;32             int right = len;33             while(left <= right)34             {35                 int mid = (left + right) >> 1;36                 if(dp[mid] < a[i])37                     left = mid + 1;38                 else39                     right = mid - 1;40             }41             dp[left] = a[i];42             if(left > len)43                 ++len;44         }45         printf("%d\n", len);46     }47     return 0;48 }
代码君


联系
我们