傳送門 ：洛谷 P1020 導彈攔截

?

?思路 : 第一問為求一段序列 的最長不下降子序列的長度?

第二問求得是 不下降子序列的個數

對于第一問，跑一邊 最長不下降子序列即可

對于第二問， 依舊是跑一邊第一問即可 (霧)

其實還要加一點神奇的位運算。。

?

#include <iostream> #include <cstdio> #include <cstring> #define Max 1000 using namespace std; int N, M; int heigh [Max], dp_1[Max], dp_2 [Max]; int dp [Max]; int Max_Answer , Total = 1; int Make (int dp [], bool flag) {for (int i = 2; i < Total; i++)for (int j = 1; j < i; j++)if (flag ^ (heigh [j] >= heigh [i])) //在這里運用了神奇的位運算，相當于一個開關， 去掉后是一個裸的跑最長不下降子序列 dp [i] = max (dp [i], dp [j] + 1); int Maxn = 1;for (int i = 1; i <= Total; i++)Maxn = max (Maxn, dp [i]); // 找出最大值 return Maxn; } int main() {ios :: sync_with_stdio (false);int x;while (cin >> heigh [Total++]){dp_1 [Total - 1] = 1; // 初始化為 每個數 之前最長不下降序列的最大長度 和 它之前 不下降序列的個數為 1 dp_2 [Total - 1] = 1;}Total--;cout << Make (dp_1, 0) << endl; cout << Make (dp_2, 1) << endl;return 0; }

?

轉載于:https://www.cnblogs.com/ZlycerQan/p/6069760.html

總結

以上是生活随笔為你收集整理的拦截导弹 (加了神奇的位运算)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。