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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/276107.html
標籤：其他