程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu1257

hdu1257

編輯:C++入門知識

首先求最多能攔截多少顆導彈,則是求一個最長下降子序列的問題。。則找到動態轉移方程。。
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]);
        }
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved