nyoj--814--又见拦截导弹(动态规划+贪心)
2024-08-31 11:38:19
- 描述
-
大家对拦截导弹那个题目应该比较熟悉了，我再叙述一下题意：某国为了防御敌国的导弹袭击，新研制出来一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能超过前一发的高度。突然有一天，雷达捕捉到敌国的导弹来袭。由于该系统存在缺陷，所以如果想把所有的导弹都拦截下来，就要多准备几套这样的导弹拦截系统。但是由于该系统成本太高，所以为了降低成本，请你计算一下最少需要多少套拦截系统。
又见拦截导弹
时间限制：3000 ms | 内存限制：65535 KB
难度：3
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 10000
int num[MAX],dp[MAX];
int main()
{
int n;
while(scanf("%d",&n)&&n!=-1)
{
for(int i=0;i<n;i++)
{
scanf("%d",&num[i]);
dp[i]=1;
}
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(num[i]>num[j]&&dp[j]+1>dp[i])
//dp数组记录当前的j属于哪一个递减数列，最后找最大值
{
dp[i]=dp[j]+1;
}
}
}
int maxx=0;
for(int i=0;i<n;i++)
{
if(maxx<dp[i]) maxx=dp[i];
}
printf("%d\n",maxx);
}
return 0;
}
最新文章
- 一张图看懂单机/集群/热备/磁盘阵列(RAID)
- sql数据库表被锁，无法查询
- CSS弹性盒模型flex在布局中的应用
- html5的感想
- rabbitMQ集群部署以及集群之间同步
- ibatis参数传递小技巧 - 疯狂的菠菜 - ITeye技术网站
- 瞎搞poj1008
- 如何去掉IE文本框后的那个X css代码
- phpstudy集成下Apache配置部署https安全证书
- Excel Open Xml中CellStyleXfs，cellStyle，cellXfs之间关系的总结
- Treat wchar_t as built-in type不一致导致的链接错误
- 转自csdn：计算机启动过程
- RyuBook1.0案例三：REST Linkage
- AndroidStudio项目提交（更新）到github最具体步骤
- Grafana学习
- 【BZOJ 3166】【HEOI 2013】Alo
- HTML5学习笔记简明版（5）：input的type超级类型
- selenium学习笔记（webdriver下载配置）
- github+hexo+node.js搭建个人博客基本过程及遇到的问题
- Qt-Creator 加入qwt库