拦截导弹问题（动态规划）-白红宇

拦截导弹问题（动态规划）

阅读量：5972 次

发布时间：2019-06-19

本文共 1714 字，大约阅读时间需要 5 分钟。

poj 1887 Testing the CATCHER

题目链接：

dp[i]表示以v[i]结尾的数列

dp[i]=max(dp[k]+1) (v[k]>v[i])

本题要注意输出

//其实最长递减序列可以转换成最长上升序列//因为其下标是递增的 #include
      
       #include
       
        #define INF 10000using namespace std;const int maxn=INF;int n;int v[maxn];int MDS(){        int Max;        int dp[maxn];        Max=0;        for(int i=1;i<=n;i++)        {            dp[i]=1;                  //一开始要将dp[i]初始化为1 WTF!!!!             for(int j=1;j
        
         dp[i]&&v[j]>v[i])                     dp[i]=dp[j]+1;            if(dp[i]>Max)                Max=dp[i];        }        return Max;}int main (){    int a,c=1;    while(cin>>a){        if(a==-1)            break;        n=1;        memset(v,0,sizeof(v));        v[n++]=a;        while(cin>>v[n]){            if(v[n]==-1){                n--;                break;            }            n++;        }         cout<<"Test #"<
         
          <<":\n"<<"  maximum possible interceptions: ";        cout<
          
           <
           
            <

View Code

HDU 1257 最少拦截系统

题目链接：

//问有最少有几个递减序列//实际上就是问最长上升序列中有多少个数（一直都不知道是怎么想到的）//最长上升序列状态转移方程：dp[i]=max(dp[k]+1),v[k]
      
       #include
       
        using namespace std;const int maxn=10000;int v[maxn],dp[maxn];int n;int MIS(){        int max=0;    for(int i=1;i<=n;i++)    {        dp[i]=1;        for(int k=1;k
        
         v[k]&&dp[k]+1>dp[i])                dp[i]=dp[k]+1;        if(dp[i]>max)                    max=dp[i];    }    return max;}int main(){        while(cin>>n){        for(int i=1;i<=n;i++)            cin>>v[i];                    cout<
         
          <