BZOJ1806 Miners 矿工配餐

目录

• BZOJ1806 Miners 矿工配餐
• 题解
• Ｃｏｄｅ

BZOJ1806 Miners 矿工配餐

题目传送门

题解

一道(Dp)题。我们记(f[i][a1][a2][b1][b2])为当前到第(i)种食物，两种煤矿前两次配送的食物分别为(a1)、(a2)和(b1)、(b2)时，能过获得的煤矿数量。然后由于这样数组肯定会爆，所以我们滚动一下即可。

Ｃｏｄｅ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('
');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int maxn=1e5+500;
char s[maxn];
int vis[4];
int n;
int f[2][4][4][4][4];
/*==================Define Area================*/
int Turn(char ch) {
	if(ch=='M') return 1;
	else if(ch=='B') return 2;
	else return 3; 
}

int Calc(int a,int b,int c) {
	vis[1]=vis[2]=vis[3]=0;
	vis[a]=1;vis[b]=1;vis[c]=1;
	return vis[1]+vis[2]+vis[3];
}

void Max(int &a,int b) {
	if(a<b) a=b;
}

int main() {
	read(n);
	scanf("%s",s);
	memset(f,-1,sizeof f);
	f[0][0][0][0][0]=0;
	for(int i=0;i<n;i++) {
		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++) {
						int x=i&1,y=!x;
						if(f[x][a1][b1][a2][b2]==-1) continue ;
						int now=Turn(s[i]);
						int C=Calc(a1,b1,now);
						Max(f[y][now][a1][a2][b2],f[x][a1][b1][a2][b2]+C);
						C=Calc(a2,b2,now);
						Max(f[y][a1][b1][now][a2],f[x][a1][b1][a2][b2]+C);
					}
				}
			}
		}
	}
	int ans=0;
	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++) {
					Max(ans,f[n&1][a1][b1][a2][b2]);
				}
			}
		}
	}
	printf("%d
",ans);
	return 0;
}