牛牛的数列 NC13134 题解备忘

题号：NC13134 链接：https://ac.nowcoder.com/acm/problem/13134 来源：牛客网

牛牛现在有一个n个数组成的数列,牛牛现在想取一个连续的子序列,并且这个子序列还必须得满足:最多只改变一个数,就可以使得这个连续的子序列是一个严格上升的子序列,牛牛想知道这个连续子序列最长的长度是多少。

链接：https://ac.nowcoder.com/acm/problem/13134 来源：牛客网

输入包括两行,第一行包括一个整数n(1 ≤ n ≤ 10^5),即数列的长度;

第二行n个整数a_i, 表示数列中的每个数(1 ≤ a_i ≤ 10^9),以空格分割。

输出一个整数,表示最长的长度。

本人较菜，不想针对题目进行研究考虑。

这道题也是典型的dp动态规划题目。

需要3个变量记录当前的状态：以当前值作为序列尾部时当前的序列最长长度，尾部值（或者下一值必须大于这个值的最小值），变化次数。

3个值确定一个状态。

状态a,b合并:如果变化次数一样，长度a>=长度b,且尾部值a<=尾部值b，那么状态a是可以替代状态b的。删掉状态b。

实际上，这个状态数量不会很多的。

另外：值为(1 ≤ a_i ≤ 10^9)，无限小用0替代。

求解：出现这些状态中的序列最长长度便是答案。

附代码:

c++

#include <string.h>
#include <vector>
using namespace std;
typedef struct Node{
	int useNum;
	int maxLen;
	int lastV = 0;
} Node;


int main() {
	int n,a;
	cin >> n;
	Node dp1[100];
	Node dp2[100];
	int dp_top1 = 0;
	int dp_top2 = 0;
	Node t0,t1;
	int maxLen=0;
	for (int i = 0; i < n; i++) {
		cin >> a;
		dp_top2 = 0;
		// 当前的值作为第一个
		dp2[dp_top2].maxLen = 1;
		dp2[dp_top2].useNum = 0;
		dp2[dp_top2].lastV = a;
		dp_top2++;

		dp2[dp_top2].maxLen = 1;
		dp2[dp_top2].useNum = 1;
		dp2[dp_top2].lastV = 0;
		dp_top2++;

		// 当前的值不作为第一个
		for (int j = 0; j < dp_top1; j++) {
			for (int k = dp1[j].useNum; k <= 1; k++) {
				// 不改变当前的值
				if (dp1[j].lastV < a) {
					dp2[dp_top2].lastV = a;
					dp2[dp_top2].maxLen = dp1[j].maxLen + 1;
					dp2[dp_top2].useNum = dp1[j].useNum;
					dp_top2++;
				}
				// 改变当前的值
				if (dp1[j].useNum + 1 <= 1) {
					dp2[dp_top2].lastV = dp1[j].lastV;
					dp2[dp_top2].maxLen = dp1[j].maxLen + 1;
					dp2[dp_top2].useNum = dp1[j].useNum + 1;
					dp_top2++;
				}
			}
		}

		// 归并
		dp_top1 = 0;
		for (int j = 0; j < dp_top2; j++) {
			bool noNeed = false;
			for (int k = 0; k < dp_top1; k++) {
				if (dp2[j].useNum == dp1[k].useNum) {
					if (dp2[j].maxLen <= dp1[k].maxLen && dp2[j].lastV >= dp1[k].lastV) {
						noNeed = true;
						break;
					}
					else if (dp2[j].maxLen >= dp1[k].maxLen && dp2[j].lastV <= dp1[k].lastV) {
						noNeed = true;
						dp1[k] = dp2[j];
						break;
					}
				}
			}
			//printf("I: 是否需要%d len:%d lastV:%d useNum:%d\n", !noNeed, dp2[j].maxLen, dp2[j].lastV, dp2[j].useNum);
			if (!noNeed) {
				dp1[dp_top1++] = dp2[j];
				if (dp2[j].maxLen > maxLen) {
					maxLen = dp2[j].maxLen;
				}
			}
		}
		//for (int j = 0; j < dp_top1; j++) {
		//	printf("I: %d-->len:%d lastV:%d useNum:%d\n", j + 1, dp1[j].maxLen, dp1[j].lastV, dp1[j].useNum);
		//}
		//printf("\n");
	}
	printf("%d\n", maxLen);
}