題目鏈接：點擊查看

題目大意：給出n個導彈的飛行高度，規定一個導彈攔截裝置只能攔截嚴格升序的導彈或嚴格降序的導彈，問攔截所有導彈需要最少多少個攔截裝置

題目分析：之前做過一個dp題，那個題目簡單，是只有攔截嚴格降序的導彈，這個題目就不能再用dp的思想了，我們其實可以考慮用搜索，將其轉化為一棵平衡二叉樹來想，每到達一個導彈我們都有四種選擇：

用之前升序的攔截系統攔截

新建一個升序的攔截系統

用之前降序的攔截系統攔截

新建一個降序的攔截系統

很顯然，我們秉承著能省則省的原則，可以查找之前用過的攔截系統能否攔截當前導彈，若可以攔截，則無需新建，否則就需要新建一個，這樣我們每一層的選擇就由四個變成了兩個，每次都要從1/2和3/4中選出兩個進行遞歸遍歷，形成一個平衡二叉樹。

如果每次都遍歷到葉子結點的話，時間復雜度未免也太大了，所以我們需要增加一個最優性剪枝，若當前的答案已經大于等于當前的最優解了，我們就可以直接回溯，在初始化時我們將答案初始化為n即可，因為最差也就是每個導彈都需要單獨的一個攔截系統，這樣就可以順利AC了，代碼寫的有點亂，不過思路清晰，我盡量加點注釋解釋一下

對了，這個題目還有點貪心的成分，比如前面已經有cnt1個升序攔截系統了，現在導彈的高度設為h，那么我們如果想用前面的攔截系統來攔截該導彈，我們肯定會選擇高度比h低的攔截系統中的最大值，這個很好想，但我不會證明，就當做顯然條件吧

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=55;int n,ans,cnt1,cnt2;//ans：答案 cnt1：上升攔截系統用了多少個 cnt2：下降攔截系統用了多少個int a[N];//每個導彈高度int up[N],down[N];//up：上升攔截系統 down：下降攔截系統void dfs(int cnt) {if(cnt1+cnt2>=ans)//最優性剪枝return; if(cnt==n+1)//若所有導彈都已分配完畢，更新答案{ans=cnt1+cnt2;return;}int mark=-1;//用來記錄最大值/最小值的標號int temp;//用來記錄最大值/最小值for(int i=1;i<=cnt1;i++)//找滿足條件的最大值{if(a[cnt]>up[i]){if(mark==-1){mark=i;temp=up[i];}else{if(temp<up[i]){mark=i;temp=up[i];}}}}if(mark!=-1)//若找到{temp=up[mark];up[mark]=a[cnt];dfs(cnt+1);up[mark]=temp;//記得回溯時還原狀態}else//若沒找到{up[++cnt1]=a[cnt];dfs(cnt+1);cnt1--;//同樣回溯時還原狀態}mark=-1;//初始化一下for(int i=1;i<=cnt2;i++)//找滿足條件的最小值{if(a[cnt]<down[i]){if(mark==-1){mark=i;temp=down[i];}else{if(temp>down[i]){mark=i;temp=down[i];}}}}if(mark!=-1)//若找到，操作同上{temp=down[mark];down[mark]=a[cnt];dfs(cnt+1);down[mark]=temp;}else//若沒找到，操作同上{down[++cnt2]=a[cnt];dfs(cnt+1);cnt2--;} }int main() { // freopen("input.txt","r",stdin);while(scanf("%d",&n)!=EOF&&n){for(int i=1;i<=n;i++)scanf("%d",a+i);ans=n;cnt1=cnt2=0;dfs(1);printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 3700 Missile Defence System.(dfs+最优性剪枝)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。