首页 > 代码库 > 动态规划_拦截导弹
动态规划_拦截导弹
被拦截的导弹应该依照飞来的高度组成一个非递增序列。求最长非递增序列的长度。
#include <iostream> using namespace std; int main() { int h[2000], d[2000], c; //h表示 高度值, d表示最优值, c是能拦截的最多导弹数 int count = 0; //统计飞来的导弹数 while (cin >> h[count++] && h[count-1]); //输入高度 d[count-1] = 1; // d[n] = 1 c = 1; //用动态规划计算全部的最优值 for (int i = count - 2; i>=0; --i) { int max = 0; for (int j = i+1; j<count; ++j) { if ((h[i] >= h[j]) && max < d[j]) max = d[j]; } d[i] = max + 1; if (c < d[i]) c = d[i]; } cout << c << endl; return 0; }
动态规划_拦截导弹
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。