之前那个写的太烂了，认真写一个

题意：

在两个矿坑中选择一个投放食品，来计算最大的满意度（因为生产的煤就相当于满意度）。其中，满意度取决于食品种类的数目。

算法：

这题题目一看就很 $dp$ 的样子。所以重点在于状态转移方程。 我们用 $dp[1][a1][a2][b1][b2]$ 来存第 $i$ 辆车去 $a$ 地前两次所放的食品 （$a1,a2$），去 $b$ 地前两次所投放的食品 （$b1,b2$） 的答案。

对于每次送，都有矿地 $a$ 与矿地 $b$ 两种情况，两种选择中，有与原先答案比较的内容。状态转移方程就出来了：

dp[i][i2][a[i]][i3][i4]=max(dp[i][i2][a[i]][i3][i4],dp[i][i1][i2][i3][i4]+_main(i1,i2,a[i])); //将 a[i] 送到矿地 a 的情况。

dp[i][i1][i2][i4][a[i]]=max(dp[i][i1][i2][i4][a[i]],dp[i-1][i1][i2][i3][i4]+_main(i3,i4,a[i])); //将 a[i] 送到矿地 b 的情况。

优化：

这道题有一个比较难的点，就是空间限制，用上面的状态转移方程会炸，那么怎么优化呢？

这里介绍一种方案叫滚动数组，它的原理很好证明：

由于第一维 $i$ 的运算只有 $i,i-1$ 这种操作，所以可以将 $i$ 对 $2$ 取模，这样，第一维数组只需要开到 $2$ 就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,dp[2][4][4][4][4]; //五维数组
int a[100001];char c[100001];
int _main(int a,int b,int c){ //计算满意度
	int cnt=1;
	if(a!=0&&a!=b&&a!=c)cnt++;
	if(b!=0&&b!=c)cnt++;
	return cnt;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++){
		if(c[i]=='M')a[i]=1;
		if(c[i]=='F')a[i]=2;
		if(c[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 i1=0;i1<=3;i1++){
			for(int i2=0;i2<=3;i2++){
				for(int i3=0;i3<=3;i3++){
					for(int i4=0;i4<=3;i4++){
						if(dp[(i-1)%2][i1][i2][i3][i4]==-1)continue;
						dp[i%2][i2][a[i]][i3][i4]=max(dp[i%2][i2][a[i]][i3][i4],dp[(i-1)%2][i1][i2][i3][i4]+_main(i1,i2,a[i])); //矿地 a
						dp[i%2][i1][i2][i4][a[i]]=max(dp[i%2][i1][i2][i4][a[i]],dp[(i-1)%2][i1][i2][i3][i4]+_main(i3,i4,a[i])); //矿地 b
					}
				}
			}
		}
	}
	int ans=-114514;
	for(int i1=0;i1<=3;i1++)for(int i2=0;i2<=3;i2++)for(int i3=0;i3<=3;i3++)for(int i4=0;i4<=3;i4++)ans=max(ans,dp[n%2][i1][i2][i3][i4]); //计算最终答案
	cout<<ans<<endl;
	return 0;
}

有错误可以提出！谢谢！！！