题目大意:有$2$个煤矿,$n$天。每天给一个煤矿送餐(共有有$3$种餐),价值为它与前面两次送餐(如果有的话)不同的种类数。最大化价值。
题解:看到只有三种餐,考虑状压$DP$。$f_{i,j,k,l,m}$表示现在是第$i$天,第一个煤矿上一次为$j$,再上一次为$k$(没有为$0$),$l,m$同理。
$$(calc(a,b,c)为求出这三个数中有多少种不为0的数)$$
$$f_{i,s_i,j,l,m} = f_{i-1,j,k,l,m} + calc(s_i,j,k)(如果f_{i-1,j,k,l,m}存在)$$
$$f_{i,j,k,s_i,l} = f_{i-1,j,k,l,m} + calc(s_i,l,m)(如果f_{i-1,j,k,l,m}存在)$$
卡点:1.加了一个假的优化
C++ Code:
#include <cstdio>
#include <cstring>
#define maxn 100010
using namespace std;
int f[2][4][4][4][4], n, s[maxn], ans;
bool v[2][4][4][4][4];
int now = 1, past = 0;
char ch[maxn];
void up(int &a, int b) {
if (b > a) a = b;
}
int tmp[4];
int calc(int a, int b, int c) {
memset(tmp, 0, sizeof tmp);
tmp[a] = tmp[b] = tmp[c] = 1;
return tmp[1] + tmp[2] + tmp[3];
}
int main() {
scanf("%d", &n);
scanf("%s", ch + 1);
for (int i = 1; i <= n; i++) s[i] = (ch[i] == 'B' ? 3 : (ch[i] == 'M' ? 1 : 2));
v[now][0][0][0][0] = true;
for (int i = 1; i <= n; i++) {
now ^= past ^= now ^= past;
memset(f[now], 0, sizeof f[now]);
memset(v[now], false, sizeof v[now]);
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 (v[past][j][k][l][m]) {
up(f[now][s[i]][j][l][m], f[past][j][k][l][m] + calc(s[i], j, k));
up(f[now][j][k][s[i]][l], f[past][j][k][l][m] + calc(s[i], l, m));
v[now][s[i]][j][l][m] = true;
v[now][j][k][s[i]][l] = true;
}
}
}
}
}
}
for (int i = 0; i < 4; i++)
for (int j = (i != 0); j < 4; j++)
for (int k = 0; k < 4; k++)
for (int l = (k != 0); l < 4; l++) up(ans, f[now][i][j][k][l]);
printf("%d\n", ans);
return 0;
}