hdu1257 dp(最长上升子序列)

题意:有一种拦截系统,可以打击导弹,但是打击的高度会逐渐下降,因此为了防御导弹攻击,就必须用多个系统,现给出一列导弹依次的高度,求最少需要的系统数。

这道题是最长上升子序列问题,但是我一开始其实并没有想到,最开始我的思路是依次剔除最长下降子序列,每剔除一轮就是需要一个拦截系统,然后直到全部数都剔除了就可以知道要几个拦截系统了。而且这样做就是最长下降子序列符合 dp 的思路也可以自圆其说,所以说为什么我成长得这么慢,其实就是我刷 dp 专题就使劲往怎么用 dp 上想而不是怎么做出来上想,很多时候这样其实我的进步还是太小。

恩,这样做 WA 了,我也不是很清楚为什么 WA ,但是我在这么敲的时候就觉得这种思路其实很乱,就这么 A 了其实对我也不太好吧。

WA 了就知道要找新办法了,于是我想到了另一种做法,边遍历数字边建系统,对于一个数字,如果之前建立过的系统中有最小值大于这个数字的,那么就说明那个系统可以拦截这枚导弹,那么就把该拦截系统的最小值改为这个数字,而如果这个数字大于所有之前拦截系统的最小值的话,那就说明没有系统可以拦截这枚导弹了,我就重新建立一个系统,其最小值就是当前数字。其实我并不知道到底是不是对的,因为有一点需要考虑,当有很多系统都能拦截它时,我该优化哪一个呢,我选择了最小的,显然我也不知道这样对不对。然后我 A 了```不甘心地 A 了```

问过学长之后,学长告诉我,其实就只是一个最长上升子序列。细想一下,对于这个最长上升子序列而言,每一个数代表一个拦截系统的最小值,并且由于序列是上升的,每一个数都不能再拦截序列中的下一个数,因为下一个数更大,因此这个子序列的长度就是拦截系统数。我觉得这个说法我更能接受,或许之前那个做法只是因为数据弱所以就这么过了吧```

就这样,我感觉我和数据一样弱```

蠢,就是蠢!

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int dp[30001],a[30001];
 6 int main(){
 7     int n;
 8     while(scanf("%d",&n)!=EOF){
 9         int i,j,c=0;
10         memset(dp,0,sizeof(dp));
11         for(i=1;i<=n;i++){
12             scanf("%d",&a[i]);
13             int f=0;
14             for(j=1;j<=c;j++){
15                 if(a[i]<dp[j]){
16                     f=1;
17                     dp[j]=a[i];
18                     break;
19                 }
20             }
21             if(!f)dp[++c]=a[i];
22             sort(dp+1,dp+c+1);
23         }
24         printf("%d\n",c);
25     }
26     return 0;
27 }

时间: 02-26

hdu1257 dp(最长上升子序列)的相关文章

最少拦截系统-----hdu1257(dp+最长上升子序列)

Problem Description 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统. Input 输入若干组数据.每组数据包括:导弹总个数(正整数

HDU 1087 &amp;&amp; POJ 2533(DP,最长上升子序列).

~~~~ 两道题的意思差不多,HDU上是求最长上升子序列的和,而POJ上就的是其长度. 貌似还有用二分写的nlogn的算法,不过这俩题n^2就可以过嘛.. ~~~~ 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1087 http://poj.org/problem?id=2533 ~~~~ HDU1087: #include<cstdio> #include<cstring> #include<algorithm> #

POJ 2250 Compromise (DP,最长公共子序列)

Compromise Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6440 Accepted: 2882 Special Judge Description In a few months the European Currency Union will become a reality. However, to join the club, the Maastricht criteria must be fulfille

poj1836——dp,最长上升子序列(lis)

poj1836——dp,最长上升子序列(lis) Alignment Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 13767   Accepted: 4450 Description In the army, a platoon is composed by n soldiers. During the morning inspection, the soldiers are aligned in a straight

codeforces340D - Bubble Sort Graph dp + 最长上升子序列

题意:给你长为n的序列 ,每个节点都和在它前面且值比他大的点产生一条边,问你一个最大 两两点没有边的集合的 集合元素有多少 解题思路:想了半天才发现是最长上升子序列.. 解题代码: 1 // File Name: 340d.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月03日 星期日 12时31分24秒 4 5 #include<vector> 6 #include<list> 7 #include<map>

hdu 1025 dp 最长上升子序列

1 //Accepted 4372 KB 140 ms 2 //dp 最长上升子序列 nlogn 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 500005; 8 int dp[imax_n]; 9 int d[imax_n]; 10 int a[imax_n]; 11 int n; 12 int len

UVA 10131 Is Bigger Smarter?(DP最长上升子序列)

Description Question 1: Is Bigger Smarter? The Problem Some people think that the bigger an elephant is, the smarter it is. To disprove this, you want to take the data on a collection of elephants and put as large a subset of this data as possible in

HDU-1257 最少拦截系统 贪心/DP 最长上升子序列的长度==最长不上升子序列的个数?

题目链接:https://cn.vjudge.net/problem/HDU-1257 题意 中文题咯中文题咯 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少

hdu 1159 Common Subsequence(dp 最长公共子序列问题LCS)

最长公共子序列问题(LCS,Longerst Common Subsequence). s1s2……si+1和t1t2……tj+1的公共子序列可能是: ①当si+1=tj+1时,在s1s2……si+1和t1t2……tj+1的公共子序列末尾追加一个. ②s1s2……si+1和t1t2……tj的公共子序列 ③s1s2……si和t1t2……tj+1的公共子序列 所以易得到递推关系dp[i+1][j+1]=  max{ dp[i][j]+1 , dp[i][j+1] , dp[i+1][j]) }  

POJ 2533 Longest Ordered Subsequence (DP最长上升子序列)

题目的大意是:给出一序列,求出该序列的最长上升子序列的最大长度. 思路: a: 1 7 3 5 9 4 8 dp: 1 2 2 3 4 3 4 #include <iostream> #include <cstring> using namespace std; const int MAXN = 1005; int main() { int n; while( cin>>n ) { int a[MAXN], dp[MAXN]; int i, j; int ans=1;