上来一看题和数据范围基本就是 DP 了，问题是状态怎么设计呢？
如果我们仅仅设 $f[i]$ 为到第 $i$ 个水果时的最大分数，那么显然会发现无法处理当前水果的分数贡献。
再来想一想我们 $DP$ 的目的是什么呢？压缩状态，去除冗余。如果我们需要统计当前水果的分数贡献，那么就需要上两次的水果是什么，状态就出来了。
$f[i][j][k][l][m]$ 为到第 $i$ 个水果时，上两个给南极的是 $j$，$k$。没有则为 $0$。上两个给北极的是 $l$，$m$ 时的最大分数，发现转移方程仍然不是很好写，考虑贡献转移法。
如果 $f[i][j][k][l][m]$ 是可行的，那么第 $i + 1$ 个水果给南极和北极都可以，两个都给下取个最值就行。
如果算到 $n - 1$ 了，那么算好 $n$ 后直接给 $ans$ 取最值就行了。
常数非常大，$64$，总共复杂度 $O(64\times n)$，手算发现超过 $1e8$ 一点点。为了避免机器故意跑的太慢，或者数据太毒瘤，我们需要进行常数优化。
可以发现：$f[i][j][k][l][m]$ 中的 $j$ 和 $k$ 以及 $l$ 和 $m$ 是没有顺序要求的，把 $j$ 和 $k$ 颠倒过来也没什么事，统计答案过程是一样的。
所以循环的时候前面小于后面，优化掉一个 $4$ 的常数，可惜我懒就算了吧。
最终时间复杂度 $O(16\times n)$，常数太大了，所以我还是把它放进来吧。
（甲组 T2 T3，太水了，不写了）
代码：
#include <cstring>
#include <iostream>
using namespace std;
int n, ans, a[200005], b[10];
int f[200005][4][4][4][4];
void ma (int &a, int b) {if (a < b) a = b;}
int main () {
cin >> n;
for (int i = 0; i < n; i ++) for (int j = 0; j < 4; j ++) for (int k = 0; k < 4; k ++) for (int l = 0; l < 4; l ++) for (int m = 0; m < 4; m ++) f[i][j][k][l][m] = -1000000000;
for (int i = 1; i <= n; i ++) cin >> a[i];
f[0][0][0][0][0] = 0;
for (int i = 0; i < n; i ++) for (int j = 0; j < 4; j ++) {
for (int k = 0; k < 4; k ++) for (int l = 0; l < 4; l ++) {
for (int m = 0; m < 4; m ++) if (f[i][j][k][l][m] >= 0) {
int sum = 0;
b[1] = b[2] = b[3] = 0;
++ b[j]; ++ b[k]; ++ b[a[i + 1] ];
for (int t = 1; t <= 3; t ++) if (b[t]) ++ sum;
ma (f[i + 1][k][a[i + 1] ][l][m], f[i][j][k][l][m] + sum);
sum = 0; b[1] = b[2] = b[3] = 0;
++ b[l]; ++ b[m]; ++ b[a[i + 1] ];
for (int t = 1; t <= 3; t ++) if (b[t]) ++ sum;
ma (f[i + 1][j][k][m][a[i + 1] ], f[i][j][k][l][m] + sum);
}
}
}
for (int i = 0; i < 4; i ++) for (int j = 0; j < 4; j ++) {
for (int k = 0; k < 4; k ++) for (int l = 0; l < 4; l ++) {
ans = max (ans, f[n][i][j][k][l]);
}
}
cout << ans;
return 0;
}
标签：YACS,分数,水果,int,题解,甲组,++,常数 From： https://www.cnblogs.com/Xy-top/p/17131977.html