算法提高之导弹防御系统

本文主要是介绍算法提高之导弹防御系统，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法提高之导弹防御系统

• 核心思想：dfs+贪心

  • 拦截导弹的进阶版，同时考虑一个点放入上升子序列还是下降子序列
  • 因为不知道该放到哪种序列，只能暴搜每个符合的都放一次
  • 然后再贪心思路看放其中哪个序列

•   #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 55;int a[N];int up[N],down[N];int n,res;//u为当前放好的导弹数 sum_up为上升的系统数void dfs(int u,int sum_up,int sum_down){if(sum_up + sum_down >= res) return;  //如果已经>=最优解res 直接returnif(u == n)  //系统数更少 同时考虑完所有导弹 一定是最优解{res = sum_up+sum_down;return;}int k=0;  //找上升子序列while(k<sum_up && up[k] >= a[u]) k++;  //当a[u] > up[k]时可以放int t = up[k];  //用于恢复现场up[k] = a[u];  //u连上if(k>=sum_up) dfs(u+1,sum_up+1,sum_down);  //当前找到的k越界 则没有可以放的 新开一个else dfs(u+1,sum_up,sum_down);up[k] = t;  //回溯k=0;while(k<sum_down && down[k] <= a[u]) k++;  //当a[u] < up[k]时可以放t = down[k];down[k] = a[u];if(k>=sum_down) dfs(u+1,sum_up,sum_down+1);  else dfs(u+1,sum_up,sum_down);down[k] = t;}int main(){while(cin>>n,n){for(int i=0;i<n;i++) cin>>a[i];res = n;dfs(0,0,0);cout<<res<<endl;}}
  

这篇关于算法提高之导弹防御系统的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---