[ 題解 ] [ 最長遞增子序列 ? / 貪心 ! ] HDU 1257 - 最少攔截系統

VJudge題目：https://cn.vjudge.net/contest/279505#problem/H

即HDU 1257 - 最少攔截系統：http://acm.hdu.edu.cn/showproblem.php?pid=1257

題意：輸入N，在同一行 !依次! 提供N個數字，表示 !依次! 來襲的飛彈的高度。

一個飛彈攔截系統一開始能攔截30000高度的飛彈，之後就不能攔截高度更大的飛彈。

比如說，當233、233和666三個飛彈 !依次! 來襲，當一個攔截系統攔截233之後就隻能攔截第二個233，不能攔截更高的666；隻能啟用第二套攔截系統。

為什麼強調 依次 ？要是飛彈能排序再來襲還需要那麼多套系統，一個系統統統攔截好了。

輸入：注意是多組資料，需要scanf()!=EOF來判斷檔案是否結束。

示例： 

Input： 

8 389 207 155 300 299 170 158 65       

Output：

2
      

我不明白這題為什麼歸入dp動态規劃專題；這明明是貪心啊。

什麼叫貪心？這道題絕對是個好栗子，貪心的典栗。先明白什麼是貪心，可以了解動态規劃的意義。

看懂題意後，假如讓你來控制攔截系統，你會怎麼做？

肯定是用能攔截目前飛彈又最弱（攔截高度最低）的系統去攔截啊！不行再啟用新系統呗。

換種說法是：

對于N個有循序的飛彈，每次都選擇攔截高度足夠 又是 其中攔截高度最低 的一套去攔截。

也就是說：

對于N個有循序的問題，每次都選擇能滿足條件 又 損失最小/獲利最大 的方案去解決問題。

這就是貪心算法的含義；在N個問題中對于每個子問題，總是都選擇目前最有利的方法，以獲得局部最優解。

為什麼是局部最優解？因為這些問題是有循序的，必須解決這個問題才能獲知下一個問題；

假如沒有循序的話，貪心會非常吃虧。比如上面所說，飛彈沒有循序的話，排序好再攔截，永遠隻需要一套系統。

為什麼貪心得不到這種更好的最優解？貪心是盲目的，不知道也不考慮以後的問題；

即使後面有對全局更有利的方法，也隻會取目前最有利的一種而對全局未必最有利的方法。

是以經常說，貪心是局部最優解算法，動态規劃是全局最優解算法。

是以貪心通常用來解決有序問題，相比之下解決無序問題的都是動态規劃。一般都能保證最終答案是最優解。

（！很多有序問題還是得用動态規劃來寫的，也有無序問題用貪心的。關鍵還是在于 全局最優解 / 局部最優解 哪個是能符合題目要求的結果。）

到這裡你應該對貪心有個大概的認識了。接下來把本題解決一下：

數組Greed[30003]存目前每套攔截系統的攔截高度。當讀入一個飛彈高度後，從數組第一個元素開始檢查：

元素數值>=讀入數值，說明能攔截，那麼用讀入數值給這個元素指派，表明它被削弱了，然後退出；

沒有元素的數值比它大，不能攔截，那麼就地存下，表示新啟用的系統的攔截高度如此。

這樣可以保證，後面的數值總是>=前面的數值，而且每次都用數值最低的系統去攔截，進而控制損失最小。

最終看看數組中有多少個數值就可以了。

聽說這題的解法叫最長遞增子序列？可能這就是那個動态規劃的解法吧；反正我用貪心搞定了。

代碼如下： 

1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int N=0;
 5 int tmp=0;
 6 int Greed[30003]={0};
 7 
 8 int main()
 9 {
10 while(scanf("%d",&N)!=EOF)
11 {
12     memset(Greed,0,sizeof(Greed));
13     
14     for(int n=1;n<=N;n++)
15     {
16         scanf("%d",&tmp);
17         for(int i=0;;i++)
18         {
19             if(Greed[i]>=tmp)
20             {
21                 Greed[i]=tmp;
22                 break;
23             }
24             else if(Greed[i]==0)
25             {
26                 Greed[i]=tmp;
27                 break;
28             }
29         }
30     }
31     
32     int i=0;
33     for(;Greed[i];i++);
34     printf("%d\n",i);
35     
36 }
37 return 0;
38 }      

轉載于:https://www.cnblogs.com/Kaidora/p/10514202.html