Hdu 1257 最少拦截系统（LIS、贪心）

No.1:

 1 #include<iostream>
 2 #include<memory.h>
 3 #include<fstream>
 4 #include<string>
 5 #include<algorithm>
 6 #include<math.h>
 7 #include<stack>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 #include<vector>
12 #include<stdio.h>
13 #include<stdlib.h>
14 #include<cstdio>
15 #include<cstdlib>
16 #include<cstring>
17 #include<cmath>
18 
19 using namespace std;
20 
21 typedef long long LL;
22 typedef long double real;
23 typedef vector<int> VI;
24 
25 
26 /**************************************************************
27     Problem:
28     Ordering:
29     Thought:
30     Result:
31 ****************************************************************/
32 
33 
34 #define INF 0x3f3f3f3f
35 #define MINN -0x3f3f3f3f
36 #define MAXN 0x3f3f3f3f
37 #define MOD 10007
38 #define NUM 5002
39 
40 
41 int n;
42 int a[NUM];
43 int dp[NUM];
44 ///最长不下降子序列
45 int LIS()
46 {
47     int res=0;
48     for(int i=0;i<n;i++)
49     {
50         dp[i]=1;
51         for(int j=0;j<i;j++)
52             if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
53         res=max(res,dp[i]);
54     }
55     return res;
56 }
57 
58 int main()
59 {
60     //freopen("dev.in","r",stdin);
61     //freopen("out.out","w",stdout);
62 
63     while(scanf("%d",&n)!=EOF)
64     {
65         for(int i=0;i<n;i++) scanf("%d",&a[i]);
66         printf("%d
",LIS());
67     }
68 
69     return 0;
70 }

No.2:

 1 /*
 2 HDU 1257
 3 by kuangbin
 4 为了使得使用的拦截系统最少，自然是要考虑使用与当前高度最接近的系统拦截（应该是贪心算法)
 5 */
 6 #include<stdio.h>
 7 #define INF 0x7ffffff
 8 #define MAXN 10000
 9 int dp[MAXN];//dp[i]代表第i个导弹当前拦截的高度
10 int main()
11 {
12     int n,x,i,res,flag;
13     int minh;
14     while(scanf("%d",&n)!=EOF)
15     {
16         res=0;
17         while(n--)
18         {
19             scanf("%d",&x);
20             flag=0;
21             minh=INF;
22             int tempi;            
23             for(i=0;i<res;i++)
24             {
25                 if(x<=dp[i]&&minh>dp[i]-x)
26                 {
27                     minh=dp[i]-x;
28                     //dp[i]=x;
29                     tempi=i;
30                     flag=1;
31                 }    
32             }
33             if(flag==0)
34             {
35                 dp[res]=x;
36                 res++;
37             }        
38             else dp[tempi]=x;
39         }
40         printf("%d
",res);    
41     }    
42     return 0;
43 }

Hdu 1257 最少拦截系统 （LIS、贪心）

Hdu 1257 最少拦截系统（LIS、贪心）