P4401 [IOI2007]Miners 矿工配餐 DP

​ 题目链接

​ 大力DP即可.

​ \(f[x][a_1][a_2][b_1][b_2]\)表示到第\(x\)天, 第一个矿洞前两天的饭是\(a_1, a_2\), 第二个矿洞前两天的饭是\(b_1, b_2\).

​ 转移 : \(f[x+1][a2][t][b1][b2] = max(f[x+1][a2][t][b1][b2], f[x][a1][a2][b1][b2] + tmp)\),

​ \(f[x+1][a1][a2][b2][t] = max(f[x+1][a1][a2][b2][t], f[x][a1][a2][b1][b2] + tmp)\);

​ 这两个方程分别表示把第\(x + 1\)天的饭给了\(1\)矿洞, \(2\)矿洞, 然后我们可以根据这三天的饭的情况算出产煤量\(tmp\).

​ 因为这个题卡空间, 所以第一位要滚掉.

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
	long long s = 0, f = 1; char ch;
	while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
	return s * f;
}

int n, ans;
char ch[100005];
int f[2][4][4][4][4];

int calc(int x, int y, int z) {
	int res = 1;
	if(x != 0 && x != y && x != z) res ++;
	if(y != 0 && y != z) res ++;
	return res;
}

int main() {
	
	n = read(); cin >> ch;
	memset(f, -1, sizeof(f)); f[0][0][0][0][0] = 0;
	for(int i = 0;i < n; i++) {
		int x = i % 2, y = (i + 1) % 2;
		for(int a1 = 0;a1 <= 3; a1++) {
			for(int a2 = 0;a2 <= 3; a2++) {
				for(int b1 = 0;b1 <= 3; b1++) {
					for(int b2 = 0;b2 <= 3; b2++) {
						if(f[x][a1][a2][b1][b2] == -1) continue ;
						int t = ch[i] == 'M' ? 1 : ch[i] == 'B' ? 2 : 3; 
						int tmp = calc(a1, a2, t);
						f[y][a2][t][b1][b2] = max(f[y][a2][t][b1][b2], f[x][a1][a2][b1][b2] + tmp);
						tmp = calc(b1, b2, t);
						f[y][a1][a2][b2][t] = max(f[y][a1][a2][b2][t], f[x][a1][a2][b1][b2] + tmp);
					}
				}
			}
		}
	}
	for(int a1 = 0;a1 <= 3; a1++) for(int a2 = 0;a2 <= 3; a2++)
		for(int b1 = 0;b1 <= 3; b1++) for(int b2 = 0;b2 <= 3; b2++) ans = max(ans, f[n % 2][a1][a2][b1][b2]);
	printf("%d", ans);

	return 0;
}