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

poj 1887 Testing the CATCHER

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

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

本题要注意输出

//其实最长递减序列可以转换成最长上升序列
//因为其下标是递增的 

#include<iostream>
#include<cstring>
#define INF 10000
using 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<i;j++)
                if(dp[j]+1>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 #"<<c<<":
"<<"  maximum possible interceptions: ";

        cout<<MDS()<<endl<<endl;
        c++;
    }
    return 0;
}

View Code


HDU 1257 最少拦截系统

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1257

//问有最少有几个递减序列
//实际上就是问最长上升序列中有多少个数（一直都不知道是怎么想到的）

//最长上升序列状态转移方程：dp[i]=max(dp[k]+1),v[k]<v[i] 如果找不到k的话，dp[i]=0 

#include<iostream>
#include<cstring>
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<i;k++)
            if(v[i]>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<<MIS()<<endl;
    }
    return 0;
}

View Code