题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1806
也是一道不错的题目呢！BZOJ上面的题的确很好呢，可惜我到现在才开始刷。不可以再把暴力+骗分尽量拿省一然后就投入文化课作为目标了，一是因为运气不一定那么好，二是我又重新发现了OI的美。如果这次可以拿到省一，我决定和之前那位大神一样，停课准备省选，哪怕这很难。
此题又涉及DP状态设计的另一个技巧，或者说要求，当发现目前的状态无法进行转移，即缺少转移所必要的条件时，就可以增加状态的维数，记录更多的信息。一开始，我们可以设dp[i]表示考虑完第i辆车最大的产煤量，显然无法进行转移，因为对于第i+1辆车，我们不知道他去哪个矿会提供多少价值，因此我们可以将状态改为dp[i][a][b][c][d]表示考虑完第i辆车，1号矿（假设的）的倒数第2辆为a，倒数第1辆为b，2号矿则分别是c和d，设第i辆车为food，则有dp[i][b][food][c][d]=max(dp[i][b][food][c][d],dp[i-1][a][b][c][d]+cnt)和dp[i][a][b][d][food]=max(dp[i][a][b][d][food],dp[i-1][a][b][c][d]+cnt)，也就是分别讨论第i辆车去哪个矿，其中cnt是第i辆车带来的价值。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 7 const int maxn = 1e5 + 5; 8 9 int dp[2][4][4][4][4]; 10 char s[maxn]; 11 12 inline int diff(int a, int b, int f) { 13 int cnt = 1; 14 if (a != 0 && a != b && a != f) ++cnt; 15 if (b != 0 && b != f) ++cnt; 16 return cnt; 17 } 18 19 int main() { 20 int n, food, ans = 0; 21 scanf("%d%s", &n, s + 1); 22 memset(dp, -1, sizeof(dp)); 23 dp[0][0][0][0][0] = 0; 24 for (int i = 1; i <= n; ++i) { 25 if (s[i] == 'M') food = 1; 26 else if (s[i] == 'F') food = 2; 27 else food = 3; 28 for (int a = 0; a <= 3; ++a) 29 for (int b = 0; b <= 3; ++b) 30 for (int c = 0; c <= 3; ++c) 31 for (int d = 0; d <= 3; ++d) { 32 if (dp[(i - 1) % 2][a][b][c][d] == -1) continue; 33 int cnt = diff(a, b, food); 34 dp[i % 2][b][food][c][d] = max(dp[i % 2][b][food][c][d], dp[(i - 1) % 2][a][b][c][d] + cnt); 35 cnt = diff(c, d, food); 36 dp[i % 2][a][b][d][food] = max(dp[i % 2][a][b][d][food], dp[(i - 1) % 2][a][b][c][d] + cnt); 37 if (i == n) ans = max(ans, max(dp[i % 2][b][food][c][d], dp[i % 2][a][b][d][food])); 38 } 39 } 40 printf("%d", ans); 41 return 0; 42 }