防御导弹---线性dp详细注释

解题思路:
线性dp

//dp[i][0]表示不去阻止第i个炮弹时的最大数(即前面i-1个炮弹的阻拦最大数)
// dp[i][1]表示组织第i个炮弹时的最大数

注意事项:
考虑前面炮弹高度等于后面炮弹高度的情况
参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 35;
int n,ans = 0;
int a[N],dp[N][5];//a[i]记录第i个炮弹的高度 

void solve(){
    memset(dp,0,sizeof(dp));
    int len = 1;
    int temp;
    while(cin>>temp){//数据输入 
        a[len++] = temp;    
    }
    for(int j = 1;j<len;j++){
        //dp[j][0]等于前面j-1个炮弹的最大阻拦数 
        dp[j][0] = max(dp[j-1][0],dp[j-1][1]);
        int i = j - 1;//用i去遍历前面的炮弹高度 
        int mx = 0,mx1=0;//用mx记录该炮弹在哪一个炮弹之后拦截，mx1临时记录最大拦截数 
        while(i>0){
            if(a[i] >= a[j]) {//前面存在炮弹高度大于等于当前炮弹高度 (注意取等于)
                if(mx1<dp[i][1]){//mx1记录的最大拦截数小于当前拦截数 
                    mx1 = dp[i][1];//更新数据 
                    mx = i;//让该炮弹在mx之后进行拦截 
                }
            }
            i--;
        }
        
        if(mx==0) dp[j][1] = 1;//说明前面没有比他高度大的炮弹 
        else{
            dp[j][1] = dp[mx][1] + 1;//有的话直接在mx的拦截数上加1 
        }
    }
    cout<<max(dp[len-1][0],dp[len-1][1]);//直接输出最后一颗导弹拦截情况的最大值 
}
int main(){ 
    solve();
    return 0;
}