目录
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+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
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\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9540028.html
相关资源：JAVA上百实例源码以及开源项目
