2023.9.1最长上升子序列

56368795

最长上升子序列：5679(严格小于号连接，LIS

最长不降子序列：56679（＜=连接,LNDS

最长下降子序列：875(LDS

最长不升子序列：665(LNIS

上升子序列最小划分数：划分成多个上升子序列，问最少分几个

5679，35，68

贪心：设d[i]表示第i个上升子序列的末尾的值（不断更新，dp表上的值越来越大）

自变量是扫到的序列编号（只会往后走，不会往前，前面的都已经排好了）

从左往右更新，即第一个总是保持最大的编号

扫到arr[1]时存到d[1]，此时d[1]=5

扫到2号时，2号为6比d[1]大，所以可以存到第一个上升子序列，更新d[1]=6

扫到3号时，比d[1]=6小，那么不能存到它后面，所以要新建一个序列，d[2]=3

扫到4号时，比和d[1]=6相等，由于是上升子序列，所以还是要存到第二个子序列里，更新d[2]=6，

扫到5号，比d[1]=6大，更新d[1]=8,

……

最后发现d数组最多到i=3位，所以最少需要3个上升子序列就可以完成对串的划分

//dp存储到第n个导弹，可以拦截多少个
// 改一下，改为以第N个导弹拦截为结尾的拦截总数
//每次来后，都可以选择拦或不拦
// 怎么体现，现在写的是确定第n个导弹拦截的情况
//打表顺序从小到大，从左到右
//一个参数是当前可拦的最大高度，不超过上一个拦的高度，凭此进行选择
//一个参数是第几个导弹
//到第n个导弹，就有N-1种选择，即上一次拦的导弹是第几个
//dp() {
//	for (int i = 1; i <= n - 1; i++) {//选择上一个拦截导弹序号
//		if (arr[n] <= arr[i]) {//只有高度不大于上一个才可以拦截
//			dp[n] = max(dp[n], dp[n - i] + 1);
//		}
//	}
//}
//要问所需的最少系统书
//贪心，让所有现在的导弹拦截高度由大到小排(优先队列，小顶堆）
//然后让这个导弹高度从最小的开始逐步往大的去比
//如果现在的高度比拦截高度最小的小
//那就让最小的更新为这个高度（即总是保留大的高度，以此来拦截未来可能更高的导弹）
//如果最小的拦不了，那就逐渐往后比，直到能比到一个比拦截高度小的
//如果都没有，那就新建一个系统，让新系统拦截这个导弹
//
// 类比哈斯图，第一问就是求最长哈斯图长度
// 第二问就是问至少需要几条链才能覆盖哈斯图
// Dilworth定理：设A种最长链长度为n,则将A种元素分成不相交的反链，反链个数至少是n
// 最大反链中元素的数目必等于最小链划分（即用最少的链数组合成一个哈斯图）中链的数目
// 什么叫不相交的反链？
// 什么是反链
// 反链是指偏序集每两个元素都是无关的子集
// 不相交的反链即是不上升子序列
// 哈斯图中，若链相交，则说明可比，即之间有连线，则一定有上升关系
// 若不相交，则不可比，那么组合在一起就是不上升子序列
// 最少的不上升子序列的个数就是最长上升子序列的长度
//
int n=0,dp[num], arr[num];
int main() {
	/*cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}*/
	int x;
	while (cin >> x) { arr[++n] = x; }
	dp[1] = 1;
	int maxnum = dp[1];
	for (int i = 2; i <= n; i++) {//dp表填完
		for (int j = 1; j <= i - 1; j++) {//每次填表的流程
			if (arr[i] <= arr[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
				maxnum = max(maxnum, dp[i]);//选择j为上一个拦截的导弹，就在上一个的基础上加上这个导弹
			}
		}
	}
	cout << maxnum << endl;
	//int cnt = 1,g[100];//至少用一个系统,至多用n个系统
	//g[1] = arr[1];//因为要拦截所有导弹，所以第一个系统必须拦截第一个导弹
	//for (int i = 1; i <= n; i++) {//从第一个导弹开始
	//	int k = 1;//指向当前系统
	//	//g[k]表示当前系统的最大拦截量，下标为系统编号
	//	while (k <= cnt && g[k] < arr[i]) { k++; }//一直访问到gk>=ai，即当前导弹能拦截了
	//	//或者超出现在已有数量，即现在系统都拦不了
	//	if (k > cnt)(g[++cnt]) = arr[i];
	//	else g[k] = arr[i];
	//}
	//cout << cnt;
	//设dpi表示以i结尾的最长不下降子序列长度
	//不下降子序列的最少个数为最长上升子序列的长度
	return 0;
}