hdu6570 动态规划 dp

题目链接：hdu6570
题目大意（机翻）:
Avin正在研究系列。 如果满足以下条件，则一个系列称为“波动”：
1）它至少包含两个元素；
2）所有位于奇数位置的元素都相同；
3）偶数位置的所有元素都相同；
4）奇数位置的元素与偶数位置的元素不同。
您得到的序列长度为n。 Avin要求您找到最长的“波浪”子系列。 子系列是系列的子序列。

第一眼看见，我就觉得他是个dp（看题解才知道暴力也行）；
我是这么考虑的在一开始
f[i][j][0/1]： 表示的是选取了第i个数字后是奇数长度还是偶数长度， 然后如果当前长度是奇数，则j代表偶数位置的数的大小是j，如果当前长度是偶数则同理。（0代表链长为偶数，1是奇数）考虑如何转移，我们知道了j之后只要去枚举1-（i-1）位置的所有数字，然后当那个位置的数是j就去选取f[k][value[i]][(0/1)^1]
就是原本是奇数你这时候就要选取偶数，原本是偶数也同理。
但是这样就是n^2,会超时，就考虑去优化。我是选择使用的
g[i][j][(0/1)]去代表着前k个数那个某个位置的数为i然后选择了i之后的长度是偶数还是奇数，与他对应的数字是j的最大长度
就从原本枚举f的1-（i-1）变成了直接拿g[j][value[i]][(0/1)^1];

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
const int inf = 1e9 + 7;
const int max_ = 1e5 + 500;
int mod = 100003;
inline int read()
{
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
int f[max_][100][3], g[100+50][100 + 50][3],n,c,node[max_];
int max(int a, int b) {
	return a > b ? a : b;
}
int main() {
	n = read(), c = read();
	for (int i = 1; i <= n; i++) {
		node[i] = read();
	}
	int ans = -1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= c; j++) {
			if (j == node[i])continue;
			//选了i后是偶，奇位置上的是j
			f[i][j][0] = g[j][node[i]][1] + 1;
			//选了i后是奇，偶位置上的是j
			f[i][j][1] = g[j][node[i]][0] + 1;
			g[node[i]][j][0] = max(g[node[i]][j][0], f[i][j][0]);
			g[node[i]][j][1] = max(g[node[i]][j][1], f[i][j][1]);
			ans = max(ans, max(f[i][j][0], f[i][j][1]));
		}
	}
	if (ans == 1) {
		cout << "0"<<endl;
		return 0;
	}
	cout << ans << endl;
	return 0;
}