1017. 怪盜基德的滑翔翼
怪盜基德是一個充滿傳奇色彩的怪盜，專門以珠寶為目標的超級盜竊犯，
而他最為突出的地方，就是他每次都能逃脫中村警部的重重圍堵，而這也很大程度上是多虧了他隨身攜帶的便于操作的滑翔翼，
有一天，怪盜基德像往常一樣偷走了一顆珍貴的鉆石，不料卻被柯南小朋友識破了偽裝，而他的滑翔翼的動力裝置也被柯南踢出的足球破壞了，
不得已，怪盜基德只能操作受損的滑翔翼逃脫，
假設城市中一共有N幢建筑排成一條線，每幢建筑的高度各不相同，
初始時，怪盜基德可以在任何一幢建筑的頂端，
他可以選擇一個方向逃跑，但是不能中途改變方向（因為中森警部會在后面追擊），
因為滑翔翼動力裝置受損，他只能往下滑行（即：只能從較高的建筑滑翔到較低的建筑），
他希望盡可能多地經過不同建筑的頂部，這樣可以級訓下降時的沖擊力，減少受傷的可能性，
請問，他最多可以經過多少幢不同建筑的頂部(包含初始時的建筑)？
輸入格式
輸入資料第一行是一個整數K，代表有K組測驗資料，
每組測驗資料包含兩行：第一行是一個整數N，代表有N幢建筑，第二行包含N個不同的整數，每一個對應一幢建筑的高度h，按照建筑的排列順序給出，
輸出格式
對于每一組測驗資料，輸出一行，包含一個整數，代表怪盜基德最多可以經過的建筑數量，
資料范圍
1≤K≤1001≤K≤100,
1≤N≤1001≤N≤100,
0<h<100000<h<10000輸入樣例：
3 8 300 207 155 299 298 170 158 65 8 65 158 170 298 299 155 207 300 10 2 1 3 4 5 6 7 8 9 10輸出樣例：
6 6 9
分析：
顯然，這是一道很裸的最長上升子序問題，
我們只需要先正著做一遍最長上升子序，然后將陣列翻轉在做一遍最長上升子序就OK了
代碼：
1 //那就是求一遍最長上升子序，然后將陣列翻轉再求一邊最長上升子序 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int N = 110; 6 7 int n; 8 int w[N]; 9 int f[N]; 10 11 void work() 12 { 13 cin >> n; 14 15 int ans = 0; 16 for (int i = 1; i <= n; i ++ ) 17 { 18 cin >> w[i]; 19 f[i] = 1; 20 for (int j = 1; j < i; j ++ ) 21 if (w[i] > w[j]) 22 f[i] = max(f[i], f[j] + 1); 23 24 ans = max(f[i], ans); 25 } 26 27 reverse(w + 1, w + 1 + n); 28 29 for (int i = 1; i <= n; i ++ ) 30 { 31 f[i] = 1; 32 for (int j = 1; j < i; j ++ ) 33 if (w[i] > w[j]) 34 f[i] = max(f[i], f[j] + 1); 35 36 ans = max(f[i], ans); 37 } 38 39 cout << ans << endl; 40 } 41 int main() 42 { 43 int T; cin >> T; 44 while (T -- ) 45 { 46 work(); 47 } 48 }View Code
1014. 登山
五一到了，ACM隊組織大家去登山觀光，隊員們發現山上一個有N個景點，并且決定按照順序來瀏覽這些景點，即每次所瀏覽景點的編號都要大于前一個瀏覽景點的編號，
同時隊員們還有另一個登山習慣，就是不連續瀏覽海拔相同的兩個景點，并且一旦開始下山，就不再向上走了，
隊員們希望在滿足上面條件的同時，盡可能多的瀏覽景點，你能幫他們找出最多可能瀏覽的景點數么？
輸入格式
第一行包含整數N，表示景點數量，
第二行包含N個整數，表示每個景點的海拔，
輸出格式
輸出一個整數，表示最多能瀏覽的景點數，
資料范圍
2≤N≤10002≤N≤1000
輸入樣例：
8 186 186 150 200 160 130 197 220輸出樣例：
4
分析：
還是一道裸的單調上升子序問題，正著求一邊，倒著求一邊，
代碼：
1 //正著求一遍最長上升子序并存起來，反著求一邊最長上升子序，并計算總序列長度 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 1010; 7 8 int n; 9 int a[N]; 10 int f[N], g[N]; 11 int ans; 12 13 int main() 14 { 15 cin >> n; 16 for (int i = 1; i <= n; i ++ ) cin >> a[i]; 17 18 for (int i = 1; i <= n; i ++ ) 19 { 20 f[i] = 1; 21 for (int j = 1; j < i; j ++ ) 22 if (a[i] > a[j]) 23 f[i] = max(f[i], f[j] + 1); 24 } 25 26 for (int i = n; i >= 1; i -- ) 27 { 28 g[i] = 1; 29 for (int j = n; j > i; j -- ) 30 if (a[i] > a[j]) 31 g[i] = max(g[i], g[j] + 1); 32 33 ans = max(ans, f[i] + g[i] - 1); 34 } 35 36 cout << ans << endl; 37 38 return 0; 39 }View Code
482. 合唱隊形
題目：
NN 位同學站成一排，音樂老師要請其中的 (N?K)(N?K) 位同學出列，使得剩下的 KK 位同學排成合唱隊形，?????
合唱隊形是指這樣的一種隊形：設 KK 位同學從左到右依次編號為 1，2…，K1，2…，K，他們的身高分別為 T1，T2，…，TKT1，T2，…，TK，??則他們的身高滿足 T1<…<Ti>Ti+1>…>TK(1≤i≤K)T1<…<Ti>Ti+1>…>TK(1≤i≤K)，?????
你的任務是，已知所有 NN 位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形，
輸入格式
輸入的第一行是一個整數 NN，表示同學的總數，
第二行有 NN 個整數，用空格分隔，第 ii 個整數 TiTi 是第 ii 位同學的身高(厘米)，
輸出格式
輸出包括一行，這一行只包含一個整數，就是最少需要幾位同學出列，
資料范圍
2≤N≤1002≤N≤100,
130≤Ti≤230130≤Ti≤230輸入樣例：
8 186 186 150 200 160 130 197 220輸出樣例：
4
分析
裸題，最長上升子序，正反來一下
代碼：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int N = 110; 6 7 int n; 8 int a[N]; 9 int f[N], g[N]; 10 11 int main() 12 { 13 cin >> n; 14 15 for (int i = 1; i <= n; i ++ ) 16 { 17 f[i] = 1; 18 cin >> a[i]; 19 for (int j = 1; j < i; j ++ ) 20 if (a[i] > a[j]) 21 f[i] = max(f[i], f[j] + 1); 22 } 23 24 int ans = 0; 25 for (int i = n; i >= 1; i -- ) 26 { 27 g[i] = 1; 28 for (int j = n; j > i; j -- ) 29 if (a[i] > a[j]) 30 g[i] = max(g[i], g[j] + 1); 31 32 ans = max(ans, f[i] + g[i] - 1); 33 } 34 35 cout << n - ans << endl; 36 37 return 0; 38 }View Code
1012. 友好城市
題目：
Palmia國有一條橫貫東西的大河，河有筆直的南北兩岸，岸上各有位置各不相同的N個城市，
北岸的每個城市有且僅有一個友好城市在南岸，而且不同城市的友好城市不相同，
每對友好城市都向政府申請在河上開辟一條直線航道連接兩個城市，但是由于河上霧太大，政府決定避免任意兩條航道交叉，以避免事故，
編程幫助政府做出一些批準和拒絕申請的決定，使得在保證任意兩條航線不相交的情況下，被批準的申請盡量多，
輸入格式
第1行，一個整數N，表示城市數，
第2行到第n+1行，每行兩個整數，中間用1個空格隔開，分別表示南岸和北岸的一對友好城市的坐標，
輸出格式
僅一行，輸出一個整數，表示政府所能批準的最多申請數，
資料范圍
1≤N≤50001≤N≤5000,
0≤xi≤100000≤xi≤10000輸入樣例：
7 22 4 2 6 10 3 15 12 9 8 17 17 4 2輸出樣例：
4
分析：
又是一個裸的最長上升子序問題，我們發現，將一條邊按照升序排序，另一邊的求一下最長上升子序就OK了，
為什么呢？為什么這么想呢？
首先，這題和順序無關，（排布排序對題目結果無影響），那么我們就給他排個序，
我們發現，只有當遞增的時候，才不會有交叉，如果出現交叉，就不合法了，那么，很顯然，求最長上升子序，
代碼：
1 //這不還是求最長單調上升子序嘛 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 5010; 7 8 struct Node 9 { 10 int x, y; 11 12 bool operator< (const Node &W) const 13 { 14 return x < W.x; 15 } 16 }a[N]; 17 18 int n; 19 int f[N]; 20 21 int main() 22 { 23 cin >> n; 24 for (int i = 1; i <= n; i ++ ) 25 { 26 int x, y; cin >> x >> y; 27 a[i] = {x, y}; 28 } 29 30 sort(a + 1, a + n + 1); 31 32 // for (int i = 1; i <= n; i ++ ) cout << a[i].x << ' ' << a[i].y << endl; 33 int ans = 0; 34 for (int i = 1; i <= n; i ++ ) 35 { 36 f[i] = 1; 37 for (int j = 1; j < i; j ++ ) 38 if (a[i].y > a[j].y) 39 f[i] = max(f[i], f[j] + 1); 40 ans = max(ans, f[i]); 41 } 42 43 cout << ans << endl; 44 45 return 0; 46 }View Code
1016. 最大上升子序列和
一個數的序列 bibi，當 b1<b2<…<bSb1<b2<…<bS 的時候，我們稱這個序列是上升的，
對于給定的一個序列(a1,a2,…,aNa1,a2,…,aN)，我們可以得到一些上升的子序列(ai1,ai2,…,aiKai1,ai2,…,aiK)，這里1≤i1<i2<…<iK≤N1≤i1<i2<…<iK≤N，
比如，對于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等，
這些子序列中和最大為18，為子序列(1,3,5,9)的和，
你的任務，就是對于給定的序列，求出最大上升子序列和，
注意，最長的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和為100，而最長上升子序列為(1,2,3)，
輸入格式
輸入的第一行是序列的長度N，
第二行給出序列中的N個整數，這些整數的取值范圍都在0到10000(可能重復)，
輸出格式
輸出一個整數，表示最大上升子序列和，
資料范圍
1≤N≤10001≤N≤1000
輸入樣例：
7 1 7 3 5 9 4 8輸出樣例：
18
分析：
還是裸的最長上升子序的題，只不過將這里維護的資訊變成了和的最大值，而不是長度
代碼：
1 //大概還是模板吧，現在維護的不再是長度了，而是最大值，更換下屬性就OK了吧 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 1010; 7 8 int n; 9 int w[N]; 10 int f[N]; 11 12 int main() 13 { 14 cin >> n; 15 int ans = 0; 16 for (int i = 1; i <= n; i ++ ) 17 { 18 cin >> w[i]; 19 f[i] = w[i]; 20 for (int j = 1; j < i; j ++ ) 21 if (w[i] > w[j]) 22 f[i] = max(f[i], f[j] + w[i]); 23 24 ans = max(ans, f[i]); 25 } 26 27 cout << ans << endl; 28 29 return 0; 30 }View Code
1010. 攔截導彈
題目
某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統，
但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度，
某天，雷達捕捉到敵國的導彈來襲，
由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈，
輸入導彈依次飛來的高度（雷達給出的高度資料是不大于30000的正整數，導彈數不超過1000），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統，
輸入格式
共一行，輸入導彈依次飛來的高度，
輸出格式
第一行包含一個整數，表示最多能攔截的導彈數，
第二行包含一個整數，表示要攔截所有導彈最少要配備的系統數，
資料范圍
雷達給出的高度資料是不大于 3000030000 的正整數，導彈數不超過 10001000，
輸入樣例：
389 207 155 300 299 170 158 65輸出樣例：
6 2
分析：
第一問就是最長上升子序的小變形，第二個就是一個貪心的思想，
第一個不用多說，很直白，第二問，就是最貪心的考慮，如果有一個攔截導彈的現有高度大于等于當前導彈高度，那就可以攔截他，
我們貪心的考慮，盡可能用更少的攔截導彈，也就是讓攔截導彈攔截的更多，那就將他放到一個大于等于導彈高度的，且所有攔截導彈中最小的一個就OK了，如果不存在就開一個新的攔截導彈，
代碼：
1 //最長下降子序，加上二分一下最小的大于當前數的值，并替換 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 1010; 7 8 int n; 9 int a[N]; 10 int f[N]; 11 int q[N]; 12 int main() 13 { 14 string line; 15 getline(cin, line); 16 stringstream ssin(line); 17 while (ssin >> a[++ n]); 18 19 // for (int i = 0; i <= n; i ++ ) cout << a[i] << ' '; 20 // cout << endl; 21 int ans = 0; 22 for (int i = 1; i <= n; i ++ ) { 23 for (int j = 1; j < i; j ++ ) 24 if (a[i] <= a[j]) 25 f[i] = max(f[i], f[j] + 1); 26 ans = max(ans, f[i]); 27 } 28 29 //思想，就是替換掉大于等于他的第一個數，如果沒有比他大的，就新開一個 30 int cnt = 0; 31 for (int i = 1; i <= n; i ++ ) 32 { 33 if (i == 1) q[cnt ++ ] = a[i]; 34 else 35 { 36 int pos = lower_bound(q, q + cnt, a[i]) - q; 37 // cout << pos << ' ' << cnt << ' ' << q[pos] << endl; 38 if (pos >= cnt) q[cnt ++ ] = a[i]; 39 else q[pos] = a[i]; 40 } 41 } 42 cout << ans << endl; 43 cout << cnt << endl; 44 }View Code
187. 導彈防御系統
題目：
為了對抗附近惡意國家的威脅，RR 國更新了他們的導彈防御系統，
一套防御系統的導彈攔截高度要么一直 嚴格單調 上升要么一直 嚴格單調 下降，
例如，一套系統先后攔截了高度為 33 和高度為 44 的兩發導彈，那么接下來該系統就只能攔截高度大于 44 的導彈，
給定即將襲來的一系列導彈的高度，請你求出至少需要多少套防御系統，就可以將它們全部擊落，
輸入格式
輸入包含多組測驗用例，
對于每個測驗用例，第一行包含整數 nn，表示來襲導彈數量，
第二行包含 nn 個不同的整數，表示每個導彈的高度，
當輸入測驗用例 n=0n=0 時，表示輸入終止，且該用例無需處理，
輸出格式
對于每個測驗用例，輸出一個占據一行的整數，表示所需的防御系統數量，
資料范圍
1≤n≤501≤n≤50
輸入樣例：
5 3 5 2 4 1 0輸出樣例：
2樣例解釋
對于給出樣例，最少需要兩套防御系統，
一套擊落高度為 3,43,4 的導彈，另一套擊落高度為 5,2,15,2,1 的導彈，
分析：
這一題有上一題變形而來，不再是只有攔截單調下降的防御系統了，而是可以攔截單調上升的或者攔截單調下降的兩種情況，
那么我們可以用貪心的思想，每次嘗試將當前高度的導彈，放到單調上升和單調下降的防御系統中，
然后，分別看，當前導彈需要新開辟一個系統還是放在已有的系統中，
這個程序需要貪心來考慮，
代碼：
1 //就是問一個序列可以拆分成最少多少個子序列，這些子序列的合法條件是，要么嚴格單調上升，要么嚴格單調下降 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 60; 7 8 int n; 9 int a[N]; 10 int up[N], down[N]; 11 //up是單調遞減的，down是單調遞增的 12 bool dfs(int depth, int u, int su, int sd) 13 { 14 if (depth < su + sd) return false; 15 if (u == n) return true; 16 17 bool flag = true; 18 for (int i = 1; i <= su; i ++ ) 19 if (up[i] < a[u]) 20 { 21 int t = up[i]; 22 up[i] = a[u]; 23 if (dfs(depth, u + 1, su, sd)) return true; 24 up[i] = t; 25 flag = false; 26 break; 27 } 28 29 if (flag) 30 { 31 up[su + 1] = a[u]; 32 if (dfs(depth, u + 1, su + 1, sd)) return true; 33 } 34 35 flag = true; 36 for (int i = 1; i <= sd; i ++ ) 37 if (down[i] > a[u]) 38 { 39 int t = down[i]; 40 down[i] = a[u]; 41 if (dfs(depth, u + 1, su, sd)) return true; 42 down[i] = t; 43 flag = false; 44 break; 45 } 46 if (flag) 47 { 48 down[sd + 1] = a[u]; 49 if (dfs(depth, u + 1, su, sd + 1)) return true; 50 } 51 return false; 52 } 53 void work() 54 { 55 for (int i = 0; i < n; i ++ ) cin >> a[i]; 56 57 //迭代加深，depth為導彈總數 58 int depth = 0; 59 while(!dfs(depth, 0, 0, 0)) depth ++ ; 60 cout << depth << endl; 61 } 62 63 int main() 64 { 65 while (cin >> n, n) 66 { 67 work(); 68 } 69 return 0; 70 }View Code
272. 最長公共上升子序列
題目：
熊大媽的奶牛在小沐沐的熏陶下開始研究資訊題目，
小沐沐先讓奶牛研究了最長上升子序列，再讓他們研究了最長公共子序列，現在又讓他們研究最長公共上升子序列了，
小沐沐說，對于兩個數列 AA 和 BB，如果它們都包含一段位置不一定連續的數，且數值是嚴格遞增的，那么稱這一段數是兩個數列的公共上升子序列，而所有的公共上升子序列中最長的就是最長公共上升子序列了，
奶牛半懂不懂，小沐沐要你來告訴奶牛什么是最長公共上升子序列，
不過，只要告訴奶牛它的長度就可以了，
數列 AA 和 BB 的長度均不超過 30003000，
輸入格式
第一行包含一個整數 NN，表示數列 A，BA，B 的長度，
第二行包含 NN 個整數，表示數列 AA，
第三行包含 NN 個整數，表示數列 BB，
輸出格式
輸出一個整數，表示最長公共上升子序列的長度，
資料范圍
1≤N≤30001≤N≤3000,序列中的數字均不超過 231?1231?1，
輸入樣例：
4 2 2 1 3 2 1 2 3輸出樣例：
2
分析：
這個題目，是最長上升子序列和最長公共子序列的結合題，
我們可以將這個題按照這兩個題目的要求，將三重回圈給寫出來，然后我們可以通過觀察狀態轉移來講代碼優化到二重回圈，
代碼：
最長公共字串的代碼
1 //為了更好的聯系知識點，這里先放入我們最長公共字串的代碼 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int N = 1010; 10 11 int n, m; 12 char a[N], b[N]; 13 int f[N][N];//表示字串a以i結尾，字符轉以j結尾的最長的匹配長度 14 15 int main() 16 { 17 cin >> n >> m; 18 cin >> a + 1 >> b + 1; 19 20 for (int i = 1; i <= n; i ++ ) 21 { 22 for (int j = 1; j <= m; j ++ ) 23 { 24 if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1); 25 else f[i][j] = max(f[i - 1][j], f[i][j - 1]); 26 } 27 } 28 29 cout << f[n][m] << endl; 30 31 return 0; 32 }View Code
最長上升子序列的代碼
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int N = 1010; 9 10 int n; 11 int a[N]; 12 int f[N];//含義：表示以i結尾的最長上升子序列的最長長度 13 14 int main() 15 { 16 cin >> n; 17 18 int ans = 0; 19 for (int i = 1; i <= n; i ++ ) 20 { 21 cin >> a[i]; 22 f[i] = 1; 23 for (int j = 1; j < i; j ++ ) 24 if (a[i] > a[j]) 25 f[i] = max(f[i], f[j] + 1); 26 ans = max(ans, f[i]); 27 } 28 29 cout << ans << endl; 30 31 return 0; 32 }View Code
最長公共上升子序列
三for代碼
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int N = 3010; 9 10 int n; 11 int a[N], b[N]; 12 int f[N][N]; 13 14 int main() 15 { 16 cin >> n; 17 for (int i = 1; i <= n; i ++ ) cin >> a[i]; 18 for (int i = 1; i <= n; i ++ ) cin >> b[i]; 19 20 for (int i = 1; i <= n; i ++ ) 21 for (int j = 1; j <= n; j ++ ) 22 if (a[i] == b[j]) 23 { 24 for (int k = 0; k < j; k ++ )//從0開始，相當于表示當前f為1了 25 if (b[k] < a[i]) 26 f[i][j] = max(f[i][j], f[i - 1][k] + 1); 27 } 28 else f[i][j] = f[i - 1][j]; 29 30 int ans = 0; 31 for (int i = 1; i <= n; i ++ ) 32 ans = max(ans, f[n][i]); 33 cout << ans << endl; 34 return 0; 35 }View Code
二for代碼
在三for代碼中，我們發現第三重for回圈，是基于當出現a[i] == b[j]的時候，然后，k從b[0]遍歷到了b[j-1]，找到了f[i][1~j-1]的最大值，
我們發現，第二層回圈j從1到n的時候，第一層回圈i是一個定值，所以條件b[k]<a[i]是固定的，因此當j增加1的時候，k的范圍也是只是
從1<=k<j變到了0<=k<j+1，所以我們只需要O(1)的檢查整數j是否會進入決策集合就OK了，那么我們用一個數val，表示每一次決策的時候
當前的1~j-1的最大值就OK了，
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int N = 3010; 9 10 int n; 11 int a[N], b[N]; 12 int f[N][N];//含義：表示以a[i]結尾的，第二維以b[j]結尾的最長公共上升子串的長度 13 14 int main() 15 { 16 cin >> n; 17 for (int i = 1; i <= n; i ++ ) cin >> a[i]; 18 for (int i = 1; i <= n; i ++ ) cin >> b[i]; 19 20 for (int i = 1; i <= n; i ++ ) 21 { 22 int val = f[i - 1][0]; 23 for (int j = 1; j <= n; j ++ ) 24 { 25 //最長公共子串 26 if (a[i] == b[j]) f[i][j] = val + 1; 27 else f[i][j] = f[i - 1][j]; 28 //找到最大的val，最長上升子串 29 if (b[j] < a[i]) val = max(val, f[i - 1][j]); 30 } 31 } 32 33 int ans = 0; 34 for (int i = 1; i <= n; i ++ ) ans = max(ans, f[n][i]); 35 cout << ans << endl; 36 37 return 0; 38 }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/276586.html
標籤：其他