思路
首先先捋清一下题意:有若干发炮弹,拦截系统拦截的导弹的高度必须是递减的,那这道题就变成了最长下降子序列了,和下面一道题类似,用动态规划求解。
用 dp[i] 表示以 i 结尾的子序列的最长长度,那么状态转移方程为:
#include<iostream> #include<vector> using namespace std; int main(){ int k; while(cin >> k){ vector<int> height(k, 0); for(int i = 0; i < k; i ++) cin >> height[i]; vector<int> dp(k, 1); int ans = 0; for(int i = 0; i < k; i ++){ for(int j = 0; j < i; j ++) if(height[j] >= height[i]) dp[i] = max(dp[i], dp[j] + 1); ans = max(ans, dp[i]); } cout << ans << endl; } return 0; }