题解 | #拦截导弹#

第一问没什么说的，跟DP9 一样，就是改成了下降序列。
第二问求个数，由于没思路，查题解查到了一个Dilworth定理
偏序集能划分成的最少的全序集个数等于最大反链的元素个数。

查到的一个比较好的博客

对本题，第二问就是求该序列“严格上升子序列最大长度”，这个数就等于所求的 下降序列个数

#include<iostream>
#include<cstring>
/*
拦截导弹
最长下降子序列  以及  子序列个数
*/
using namespace std;
const int MAXN  = 1000+1;
int arr[MAXN];
int dp[MAXN];

int getLen(int n){
	int res = 0;
	//记录全数组的最长序列长度
	for (int i = 0; i < n; ++i){
		dp[i] = 1;
		for (int j = 0; j < i; ++j){
			if(arr[i] <= arr[j]){
				//题目要求的 不高于前一个
				//如果比前面某个数小于等于，则可以续到他后面
				dp[i] = max(dp[i],dp[j] + 1);
			}
		}
		res = max(dp[i],res);
		//每经历一个 i 比较并更新一下整个数组的最长序列res
	}
	return res;
}

int getNum(int n){
	int res = 0;
	//记录全数组的最长序列长度
	for (int i = 0; i < n; ++i){
		dp[i] = 1;
		for (int j = 0; j < i; ++j){
			//Dilworth  要求  严格
			if(arr[i] > arr[j]){
				dp[i] = max(dp[i],dp[j] + 1);
			}
		}
		res = max(dp[i],res);
		//每经历一个 i 比较并更新一下整个数组的最长序列res
	}
	return res;
}


int main(){
	int n;
	cin>>n;
	memset(dp,0,sizeof(dp));

	for (int i = 0; i < n; ++i){
		cin>>arr[i];
	}
	//最长下降子序列长度
	cout<<getLen(n)<<endl;
	//重点  求数组中下降序列个数
	//Dilworth 定理。对本题，这个个数就等于 最长严格上升子序列长度
	memset(dp,0,sizeof(dp));
	cout<<getNum(n)<<endl;
	
	return 0;
}