题解 | 拦截导弹

#include <bits/stdc++.h>
using namespace std;

const int SIZE=25;

int dp[SIZE];

int main(){
    int n;
    while(cin>>n){
        memset(dp,INT_MIN,sizeof(dp));
        int a[n];
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int ans=0;
        for(int i=0;i<n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(a[j]>=a[i])dp[i]=max(dp[i],dp[j]+1);
            }
            ans=max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
}

这个问题是查询最大下降长度，属于前面解决的问题，最大子序列长度的变体，问题本质是只允许下降的情况下，去扫描尽可能多的内容，那么，我们就可以这样做这个状态转移方程，对于一个节点，这个自然结果就是1，如果是两个，左侧的比它高，结果就是2，如果比它低当前节点的结果就是1，如果是三个，我们可以发现，也不需要分析前面的第一个，而是直接看前面到底有多少个最大的即可，这样就得到了方程，然后就可以得到，初始状态，每个都一定是1，如果左侧错在一个符合条件的，那么就可以加一，但是可以发现一点，存在递归性质的是，左侧假如本身存在了一些状态的存储，也就是他本身就存在一些下降的结果，那么，后面的就可以直接加一比较一下即可得到自身的新状态。