「IOI 2007」矿工配餐

Description

题目链接:BZOJ 1806

现有两个煤矿,每个煤矿都雇用一组矿工。采煤工作很辛苦,所以矿工们需要良好饮食。每当一辆食品车到达煤矿时,矿工们便会产出一定数量的煤。

$n​$ 辆食品车分为三种类型:肉车,鱼车和面包车。矿工们喜欢变化的食谱。如果提供的食品能够不断变化,他们的产煤量将会增加。每当一个新的食品车到达煤矿时,矿工们就会比较这种新的食品和前两次(或者少于两次,如果前面运送食品的次数不足两次)的食品,并且:

  • 如果这几次食品车都是同一类型的食品,则矿工们产出一个单位的煤。
  • 如果这几次食品车中有两种不同类型的食品,则矿工们产出两个单位的煤。
  • 如果这几次食品车中有三种不同类型的食品,则矿工们产出三个单位的煤。

预先已知食品车的类型及其被配送的顺序。食品车不能被拆分,每个食品车必须被全部送到一个或另一个煤矿。求出两个煤矿的产煤量的总和的最大值。

数据范围:$1\le n\le 10^5$


Solution

我们定义 $\text{DP}$ 状态 $f_{i,a,b,c,d}$:考虑完第 $i$ 个食品车,第一个煤矿前 $2$ 个食品车为 $a,b$,第二个煤矿前 $2$ 个食品车为 $c,d$。我们可以枚举写一个食品车 $x​$ 到达哪个煤矿,直接转移即可。对于三个食品的贡献,我们可以写一个函数分类讨论

注意:$\text{DP}$ 转移过程中,可能会遇到不合法的状态(比如 $a=0,b>0$,我们可以通过 $f​$ 数组的值来判断状态是否合法)。

对于 $\text{DP}$ 的写法,可能递归写起来更简短。但是本题卡空间($18\text{MB}$)!只能写递推并使用滚动数组

时间复杂度:$O(4^4\cdot n)$


Code

递推(MLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>

const int N=1e5+5;
char s[N];
int n,p[N],f[N][4][4][4][4];

int get(int a,int b,int c) {
if(!a&&!b) return 1;
if(!a) return b!=c?2:1;
return a==b&&b==c?1:(a!=b)+(b!=c)+(c!=a);
}
int dfs(int x,int a,int b,int c,int d) {
if(x>n) return 0;
int &ans=f[x][a][b][c][d];
if(ans) return ans;
return ans=std::max(dfs(x+1,b,p[x],c,d)+get(a,b,p[x]),dfs(x+1,a,b,d,p[x])+get(c,d,p[x]));
}
int main() {
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;++i) p[i]=s[i]=='M'?1:s[i]=='F'?2:3;
printf("%d\n",dfs(1,0,0,0,0));
return 0;
}

递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <cstring>
#include <algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;++i)

const int N=1e5+5;
char s[N];
int n,f[4][4][4][4];

int get(int a,int b,int c) {
if(!a&&!b) return 1;
if(!a) return b!=c?2:1;
return a==b&&b==c?1:(a!=b)+(b!=c)+(c!=a);
}
void chkmax(int &x,int y) {
x=x>y?x:y;
}
int main() {
scanf("%d%s",&n,s+1);
memset(f,-1,sizeof(f));
f[0][0][0][0]=0;
FOR(_,1,n) {
int g[4][4][4][4],o=(s[_]=='M'?1:s[_]=='F'?2:3);
memset(g,-1,sizeof(g));
FOR(i,0,3) FOR(j,0,3) FOR(k,0,3) FOR(l,0,3) {
if(f[i][j][k][l]<0) continue;
chkmax(g[j][o][k][l],f[i][j][k][l]+get(i,j,o));
chkmax(g[i][j][l][o],f[i][j][k][l]+get(k,l,o));
}
memcpy(f,g,sizeof(g));
}
int ans=0;
FOR(i,0,3) FOR(j,0,3) FOR(k,0,3) FOR(l,0,3) chkmax(ans,f[i][j][k][l]);
printf("%d\n",ans);
return 0;
}
0%