最少拦截系统
拿到这道题的时候,是刚开始接触dp,今晚又看到它了,觉得它应该算是一道比较经典的dp题,因此,就又拿出来看了
这道题重要的是看懂题意,我做的时候,刚开始总wa,后来才明白题意理解错了
题意:面对敌方陆续打来的导弹,我方需要配备几套拦截系统,才能拦截敌人所有的导弹(拦截系统所能拦截的导弹的高度必须低于上次此套系统拦截的导弹的高度,第一次拦截的高度H < 30000)
例如,导弹打来的高度依次为
data[N] 389 207 155 300 299 170 158 65
sum[N] 1 1 1 2 2 2 2 1
上图中1,2即是拦截系统的编号,sum[N]数组存储的是相应位置上的炮弹被哪套拦截系统所拦截
解题思路:遍历data数组,同时跟前面的数作比较,如果高于前面的数就加1,,
Description
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
Output
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
现给出代码:
#include <iostream>
#include<cstdio>
#include<string.h>
using namespace std;
int main()
{
int M,N;
int data[1000+10];
int dp[1000];
int i, j;
while(~scanf("%d",&M))
{
for(i = 0; i < M; i++)
{
scanf("%d",&data[i]);
dp[i]=1;
}
for(i = 0; i < M; i++)
{
for(j = 0; j < i;j++)
{
if(data[i] > data[j])
{
dp[i] = max(dp[i],dp[j]+1);//更新
}
}
}
int ans = 0;
for(i = 0; i < M; i++)
{
ans = max(ans,dp[i]);
}
printf("%d\n",ans);
}
return 0;
}