一题目【问题描述】某国为了防御敌国的导弹袭击开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭并观测到导弹依次飞来的高度请计算这套系统最多能拦截多少导弹。拦截来袭导弹时必须按来袭导弹袭击的时间顺序不允许先拦截后面的导弹再拦截前面的导弹。【输入形式】每组输入有两行第一行输入雷达捕捉到的敌国导弹的数量kk25第二行输入k个正整数表示k枚导弹的高度按来袭导弹的袭击时间顺序给出以空格分隔。【输出形式】每组输出只有一行包含一个整数表示最多能拦截多少枚导弹。【样例输入】8 300 207 155 300 299 170 158 65【样例输出】6二解题方法首先跟据题意这道题是一个最长递减子序列问题因此可以采用动态规划或者dfs剪枝来实现在这篇文章我们采用后者本题的动态规划算法解析在另一篇文章。三思路历程因为k25,因此dfs大概不会出现超时的情况那么dfs的核心步骤便是当前炮弹是否加入到当前最长递减子序列中在没有优化的情况下应该为2^n因此我们可以添加一个记忆数组memo来避免重复运算memo[idx][last]表示从idx个导弹并且在前一个被拦截导弹的下标为last时往后还能最多拦截多少个导弹。四代码#includebits/stdc.h using namespace std; int arr[30]; int n; int memo[30][30]; //memo记忆化数组 避免递归中的重复计算 用于降低时间复杂度 //memo[idx][last] 从第 idx 个导弹开始且前一个已经拦截的导弹是第 last 个时最多还能拦截多少枚导弹。 int dfs(int idx,int last)//从第idx个导弹开始 上一发被拦截导弹的索引 { if(idxn)return 0; if(memo[idx][last]!-1)return memo[idx][last]; int resdfs(idx1,last); //表示不拦截第idx个导弹 if(last0||arr[idx]arr[last]){ resmax(res,dfs(idx1,idx)1); //判断拦截第idx发导弹和不拦截第idx发导弹 //取res为二者最大值 } return memo[idx][last]res; } int main() { cinn; for(int i1;in;i) { cinarr[i]; } memset(memo,-1,sizeof(memo)); coutdfs(1,0)endl; return 0; }