首先求最多能攔截多少顆導彈,則是求一個最長下降子序列的問題。。則找到動態轉移方程。。
dp[i]=max(dp[j])+1,ja[i],因為dp[j]所表示的就是一個有序下降子序列。。。所以加進來也將是一個有序上升數列。。
然後是最少需要多少套導彈系統。。。有點貪心的做法。。就是要攔截導彈,盡量用小的去攔截可以攔截的導彈。。最後得到的導彈系統套數是最少的。。
題目鏈接:
點擊打開鏈接
代碼如下:
#include#include const int maxn=100000+10; int dp1[maxn],dp2[maxn],a[maxn],n=0; int DP1(int k) { int ans=1; dp1[1]=1; for(int i=2;i<=k;i++) { int Max=0; for(int j=1;jMax&&a[j]>a[i]) Max=dp1[j]; } dp1[i]=Max+1; if(dp1[i]>ans) ans=dp1[i]; } return ans; } int DP2(int k) { int ans=1; dp2[1]=1; for(int i=2;i<=k;i++) { int Max=0; for(int j=1;jMax&&a[j]ans) ans=dp2[i]; } return ans; } int main() { int i,ans[2],sum; while(scanf("%d",&sum)!=EOF) { for(int i=1;i<=sum;i++) scanf("%d",&a[i]); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); ans[0]=DP1(sum); ans[1]=DP2(sum); //printf("%d\n",ans[0]); printf("%d\n",ans[1]); } }