[数据结构与算法]AcWing 187 导弹防御系统 题解（动态规划—DP—LIS）

原题

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 55;

int n;
int ans;//记录总最少序列的个数
int a[N]; 
int up[N];//记录每个上升序列的结尾的数
int down[N];//记录每个下降序列的结尾的数

void dfs(int z, int u, int d){//z表示目前遍历到的序列元素序号， u表示上升序列的数量，d表示下降序列的数量 
	if(u + d >= ans) return;//如果上升和下降序列和已经大于或等于最小序列数，就不可能再产生更少的序列数，直接退出即可
	if(z == n){//如果已经遍历到这个样例的最后一个数，就可以返回的答案了 
		ans = u + d;
		return ;
	} 
	
	//上升序列 
	int k = 0;//k表示目前遍历到的序列总数
	while(k < u && up[k] >= a[z]) k ++ ;//如果当前上升序列的最后一个数大于等于当前遍历到的元素，就继续往后遍历下一个上升序列
	int t = up[k];//记录结尾元素，用于恢复现场
	up[k] = a[z];//遍历到合适的上升序列后，就将当前元素加入到上升序列的结尾
	if(k < u) dfs(z + 1, u, d);//如果k小于u,表示当前还没有遍历到最后的空的上升序列，所以就不用新加上升序列，所以上升序列的个数不变，加入原始序列的新的需要遍历的元素，开始新的遍历
	else dfs(z + 1, u + 1, d);//如过k = u，表示当前遍历的元素已经加入到最后的空的上升序列中，这时需要新建立一个上升序列，所以u + 1
	up[k] = t;//恢复现场 
	
	//下降序列 
	k = 0;  
	while(k < d && down[k] <= a[z]) k ++ ;//如果当前下降序列的最后一个数大于等于当前遍历到的元素，就继续往后遍历下一个上升序列
	t = down[k];
	down[k] = a[z];
	if(k < d) dfs(z + 1, u, d);//与上述上升序列同理 
	else dfs(z + 1, u , d + 1);//与上述上升序列同理
	down[k] = t; 
} 

int main()
{
	while(cin>>n, n){
		for(int i = 0; i < n; i ++ ) cin>>a[i];
		
		ans = n;//将最大序列数设为元素数，即给dfs设置边界
		
		dfs(0, 0, 0);//刚开始所有序列的数量都是0
		
		cout<<ans<<endl; 
	}
	return 0;
}