「IOI 2007」矿工配餐

发表于 | | 阅读次数:
字数统计: 947 字

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%