暴力解法 | #拦截导弹# 假如不会Dilworth定理

Dilworth定理:

最少的下降序列个数就等于整个序列最长上升子序列的长度

大部分答案都是基于这个，但这个数学定理还蛮冷门的，临时遇到肯定不会做，所以再多写了一个暴力解

求最长递减子序列还是用传统dp

同时用一系列队列来模拟排队过程

策略是拿到一个数字看看已有队列能不能放下它

如果有，把它放在队尾数字最小的队列之后

如果没有，则新开一个队列

因为导弹最多一千枚，复杂度倒是没有很夸张

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,t,i,j;
    cin>>n;
    vector<pair<int, int>> dp(n,{1,1});//第一个元素代表最多拦截数量，第二个元素代表组合数
    //一个是最多，一个是最优组合
    vector<int> nums(n);
    int result1=0,result2=0;
   // cout<<n<<endl;
    dp[0]={1,1};
    for(i=0;i<n;++i){
        cin>>nums[i];
        for(j=0;j<i;++j){
            if(nums[i]<=nums[j]){
                //延续原有序列
                dp[i].first=max(dp[i].first,dp[j].first+1);
            }else{
                dp[i].second=max(dp[i].second,dp[j].second+1);
            }
        }
        result1=max(result1,dp[i].first);
        result2=max(result2,dp[i].second);
       // cout<<dp[i].first<<' '<<dp[i].second<<endl;

        }
        cout<<result1 <<endl<<result2<<endl;
        return 0;

    }

#include <climits>
#include <iostream>
#include <deque>
using namespace std;

int main() {
    int n,t,i,j,result1=0,result2;
    cin>>n;
   deque<deque<int>> dp; //暴力解法，保存每个导弹
   deque<int> nums,dp1(n,1);
   int last;
   deque<int>* p;
   for(i=0;i<n;++i){
        cin>>t;
        nums.push_back(t);
        p=nullptr;
        last = INT_MAX;
        for(deque<int> &k:dp){
            if(k.back()>=t && k.back()<last){
                last=k.back();
                p=&k;
            }
        }

        if(!p){dp.push_back({t});}else{
            p->push_back(t);
        }

        for(j=0;j<i;++j){
            if(nums[j]>=nums[i])dp1[i]=max(dp1[i],dp1[j]+1);
        }
        result1=max(dp1[i],result1);

   }
  //print2d(dp);
   cout<<result1<<endl<<dp.size()<<endl;

} 

// 64 位输出请用 printf("%lld")