[TIOJ] 1344. [IOI 2007, Day 2] Miners

題目連結:http://tioj.infor.org/problems/1344

---

DP題，一開始我只想到$2 \cdot 4^5 N$的作法，但估了一估感覺不是很能跑，而且code也不是很好寫，後來聽了講解之後才知道狀態其實可以比我預期的少。
狀態是$dp[i][a_1][a_2][b_1][b_2]$，代表要處理第$i$個餐點，而先前第一區已有$a_1, a_2$號餐點，而第二區則有$b_1, b_2$號餐點，那轉移其實也還好，就是$dp[i+1][a_2][type(str_i)][b_1][b_2] = dp[i][a_1][a_2][b_1][b_2]+G(type(str_i), a_1, a_2)$(轉給第二區也是同樣的方式)，其中G函數為計算那三個中的種類的函數。

#include <bits/stdc++.h>
using namespace std;
const int N = 100001;

char str[N];
int dp[2][4][4][4][4], toId[256];

inline int G(int,int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	memset(dp, -1, sizeof(dp));
	toId[(int)'M']=1;
	toId[(int)'B']=2;
	toId[(int)'F']=3;
	int n; cin>>n;
	cin>>str;
	dp[0][0][0][0][0]=0;
	int pos=0;
	for(int i=0;i<n;i++){
		for(int a=0;a<4;a++){
			for(int b=0;b<4;b++){
				for(int c=0;c<4;c++){
					for(int d=0;d<4;d++){
						if(dp[pos][a][b][c][d] == -1) continue;
						dp[pos^1][b][toId[(int)str[i]]][c][d] = max(dp[pos^1][b][toId[(int)str[i]]][c][d], dp[pos][a][b][c][d]+G(toId[(int)str[i]],a,b));
						dp[pos^1][a][b][d][toId[(int)str[i]]] = max(dp[pos^1][a][b][d][toId[(int)str[i]]], dp[pos][a][b][c][d]+G(toId[(int)str[i]],c,d));
						dp[pos][a][b][c][d] = -1;
					}
				}
			}
		}
		pos^=1;
	}
	int ans = 0;
	for(int a=0;a<4;a++) for(int b=0;b<4;b++) for(int c=0;c<4;c++) for(int d=0;d<4;d++)
		ans = max(ans, dp[pos][a][b][c][d]);
	cout<<ans<<'\n';
	return 0;
}

inline int G(int a, int b, int c){
	bitset<4> bb;
	bb[a]=1;
	bb[b]=1;
	bb[c]=1;
	bb[0]=0;
	return bb.count();
}