那么一大篇的題目描述還真是嚇人。

仔細(xì)一讀其實(shí)就是一個(gè)LIS，還無(wú)任何變形。

剛剛學(xué)會(huì)了個(gè)二分優(yōu)化的DP，1A無(wú)壓力。

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 LOCAL 14 freopen("1950in.txt", "r", stdin); 15 #endif 16 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 else 39 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 } 代碼君

轉(zhuǎn)載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/3863630.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的HDU 1950 Bridging signals的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。