题解 P4401 【[IOI2007]Miners 矿工配餐】
TRZ_2007
2020-08-13 14:52:30
**[题解 P4401 【[IOI2007]Miners 矿工配餐】](https://www.luogu.com.cn/problem/P4401)**
# Solution
其实重点就是这三句：
- 1：如果这几次食品车都是同一类型的食品，则矿工们产出一个单位的煤。
- 2：如果这几次食品车中有两种不同类型的食品，则矿工们产出两个单位的煤。
- 3：如果这几次食品车中有三种不同类型的食品，则矿工们产出三个单位的煤。
看懂了这三句后，我们来想动规。
**状态定义**：看见有 $n$ 个物品，首先我们就要想到定义 $f(n)$ 表示送完第 $n$ 个物品后产煤量的最大值，因为产煤量和前面两次送的食物有关，所以我们引用LJ的名言：**加一维**，只不过这里要加4维罢了，于是乎最后的定义是：$f(n,a,b,c,d)$ 表示送完第 $n$ 个物品后且一号矿洞前两次的食物为 $a$ 和 $b$，二号矿洞前两次的食物为 $c$ 和 $d$ 。
**转移方程**：显然，对于每一种食物，我们既可以把它放入一号矿洞，也可以把它放入二号矿洞，我们可以计算出放入这些矿洞后的产煤数，并取一个最大值即可。
所以我们可以得到如下代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
char s[N];
int n,len,a[N],ans = 0;
int dp[N][4][4][4][4];
int calc(int nw,int i,int j) {
int cnt = 1;
if(nw && nw != i && nw != j) cnt++;
if(i && i != j) cnt++;
return cnt;
}
int main() {
scanf("%d",&n);
scanf("%s",s + 1);
for(int i = 1;i <= n;i++) { // 为了方便计算，我们在这里把它转成数字
if(s[i] == 'M') a[i] = 1;
if(s[i] == 'F') a[i] = 2;
if(s[i] == 'B') a[i] = 3;
}
memset(dp,-1,sizeof(dp)); //最初时所有状态都不存在
dp[0][0][0][0][0] = 0; //初始化状态
for(int i = 1;i <= n;i++) {
for(int a1 = 0;a1 < 4;a1++) { //枚举所有的可能性
for(int a2 = 0;a2 < 4;a2++) {
for(int b1 = 0;b1 < 4;b1++) {
for(int b2 = 0;b2 < 4;b2++) {
if(dp[i - 1][a1][a2][b1][b2] == -1) continue;
int tmp1 = dp[i - 1][a1][a2][b1][b2] + calc(a1,a2,a[i]); //计算把煤放入一号矿洞的收益
int tmp2 = dp[i - 1][a1][a2][b1][b2] + calc(b1,b2,a[i]); //计算把煤放入二号矿洞的收益
dp[i][a2][a[i]][b1][b2] = max(dp[i][a2][a[i]][b1][b2],tmp1);
dp[i][a1][a2][b2][a[i]] = max(dp[i][a1][a2][b2][a[i]],tmp2);
} //对其取最大值
}
}
}
}
for(int a1 = 0;a1 < 4;a1++) { //枚举可能解
for(int a2 = 0;a2 < 4;a2++) {
for(int b1 = 0;b1 < 4;b1++) {
for(int b2 = 0;b2 < 4;b2++) {
ans = max(ans,dp[n][a1][a2][b1][b2]);
}
}
}
}
printf("%d\n",ans);
return 0;
}
```
当你兴致冲冲地打完代码后，你会发现它MLE了。
为什么？因为这份代码的空间复杂度达到了 $\Theta(256N)$，面对 18 MB 的空间限制无疑会爆炸。
怎么办？我们需要加优化，关于第一维的 $i$，我们发现它只和 $i-1$ 有关，所以我们对于 $i$ 和 $i-1$ 将其对 2 取模，结果不会受到影响。
最后的 AC 代码如下：
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
int f[2][4][4][4][4];
char s[N];
int a[N],ans,n;
int turn(char ch) {
if(ch == 'M') return 1;
if(ch == 'F') return 2;
if(ch == 'B') return 3;
}
int calc(int nw,int i,int j) {
int cnt = 1;
if(nw && nw != i && nw != j) cnt++;
if(i && i != j) cnt++;
return cnt;
}
int main() {
scanf("%d",&n);
scanf("%s",s + 1);
for(int i = 1;i <= n;i++) {
a[i] = turn(s[i]);
}
memset(f,-1,sizeof(f));
f[0][0][0][0][0] = 0;
for(int i = 1;i <= n;i++) {
for(int a1 = 0;a1 < 4;a1++) {
for(int b1 = 0;b1 < 4;b1++) {
for(int a2 = 0;a2 < 4;a2++) {
for(int b2 = 0;b2 < 4;b2++) {
if(f[(i - 1) % 2][a1][b1][a2][b2] == -1) continue;
int tmp1 = f[(i - 1) % 2][a1][b1][a2][b2] + calc(a1,b1,a[i]);
int tmp2 = f[(i - 1) % 2][a1][b1][a2][b2] + calc(a2,b2,a[i]);
f[i % 2][b1][a[i]][a2][b2] = max(f[i % 2][b1][a[i]][a2][b2],tmp1);
f[i % 2][a1][b1][b2][a[i]] = max(f[i % 2][a1][b1][b2][a[i]],tmp2);
}
}
}
}
}
for(int a1 = 0;a1 < 4;a1++) {
for(int b1 = 0;b1 < 4;b1++) {
for(int a2 = 0;a2 < 4;a2++) {
for(int b2 = 0;b2 < 4;b2++) {
ans = max(ans,f[n % 2][a1][b1][a2][b2]);
}
}
}
}
printf("%d\n",ans);
return 0;
}
```