动态规划——导弹拦截

导弹拦截"/>

动态规划——导弹拦截

动态规划——导弹拦截

P1020 [NOIP1999 普及组] 导弹拦截

解题思路

首先这道题我们需要求出最长的上升序列 和最长的非上升序列

主要用到了lower_bound 和upper_bound函数 ，前者包括了大于等于，而后者仅含大于

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define rep(i,s,n) for(long long i=s;i<n;i++)
#define reb(i,d,n) for(long long i=n;i>=d;i--)
using namespace std;
const int SIZE = 100001;
int res[SIZE];
int dp1[SIZE];
int dp2[SIZE];
inline bool read(int& x) {char c = getchar();if (c == EOF)return false;while (c > '9' || c < '0')c = getchar();while (c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return true;
}
signed main()
{ios::sync_with_stdio(false);int i = 0;cin >> res[0];int len1 = 1;int len2 = 1;dp1[1] = res[0];dp2[1] = res[0];int temp;while (cin>>temp){if (temp <= dp1[len1]){dp1[++len1] = temp;}else{*upper_bound(dp1+1, dp1+1 + len1 , temp, greater<int>()) = temp;//dp1中第一个小于temp得数 是一个下降序列}if (temp > dp2[len2]){dp2[++len2] = temp;}else{*lower_bound(dp2+1, dp2 +1+ len2 , temp) = temp;//dp2中第一个大于等于temp得数 是一个上升序列}}cout << len1 << endl << len2;return 0;}

注意

输入 cin>>temp 需要注意

upper_bound greater 是指第一个比该数小的位置

总的来说upper和lower需要 和前面是否有等于号匹配