Voldemort's blog

Voldemort's blog

我好菜啊

题解 P4401 【[IOI2007]Miners 矿工配餐】

posted on 2020-08-13 14:52:30 | under 题解 |

题解 P4401 【[IOI2007]Miners 矿工配餐】

Solution

其实重点就是这三句:

  • 1:如果这几次食品车都是同一类型的食品,则矿工们产出一个单位的煤。

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

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

看懂了这三句后,我们来想动规。
状态定义:看见有 $n$ 个物品,首先我们就要想到定义 $f(n)$ 表示送完第 $n$ 个物品后产煤量的最大值,因为产煤量和前面两次送的食物有关,所以我们引用LJ的名言:加一维,只不过这里要加4维罢了,于是乎最后的定义是: $f(n,a,b,c,d)$ 表示送完第 $n$ 个物品后且一号矿洞前两次的食物为 $a$ 和 $b$,二号矿洞前两次的食物为 $c$ 和 $d$ 。
转移方程:显然,对于每一种食物,我们既可以把它放入一号矿洞,也可以把它放入二号矿洞,我们可以计算出放入这些矿洞后的产煤数,并取一个最大值即可。

所以我们可以得到如下代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 100009;

char s[N];
int n,len,a[N],ans = 0;

int dp[N][4][4][4][4];

int calc(int nw,int i,int j) {
    int cnt = 1;
    if(nw && nw != i && nw != j) cnt++;
    if(i && i != j) cnt++;
    return cnt;
}

int main() {
    scanf("%d",&n);
    scanf("%s",s + 1);
    for(int i = 1;i <= n;i++) { //  为了方便计算,我们在这里把它转成数字
        if(s[i] == 'M') a[i] = 1;
        if(s[i] == 'F') a[i] = 2;
        if(s[i] == 'B') a[i] = 3;
    }
    memset(dp,-1,sizeof(dp));   //最初时所有状态都不存在
    dp[0][0][0][0][0] = 0;  //初始化状态
    for(int i = 1;i <= n;i++) {
        for(int a1 = 0;a1 < 4;a1++) {   //枚举所有的可能性
            for(int a2 = 0;a2 < 4;a2++) {
                for(int b1 = 0;b1 < 4;b1++) {
                    for(int b2 = 0;b2 < 4;b2++) {
                        if(dp[i - 1][a1][a2][b1][b2] == -1) continue;
                        int tmp1 = dp[i - 1][a1][a2][b1][b2] + calc(a1,a2,a[i]);    //计算把煤放入一号矿洞的收益
                        int tmp2 = dp[i - 1][a1][a2][b1][b2] + calc(b1,b2,a[i]);    //计算把煤放入二号矿洞的收益
                        dp[i][a2][a[i]][b1][b2] = max(dp[i][a2][a[i]][b1][b2],tmp1);
                        dp[i][a1][a2][b2][a[i]] = max(dp[i][a1][a2][b2][a[i]],tmp2);
                    }   //对其取最大值
                }
            }
        }
    }
    for(int a1 = 0;a1 < 4;a1++) {   //枚举可能解
        for(int a2 = 0;a2 < 4;a2++) {
            for(int b1 = 0;b1 < 4;b1++) {
                for(int b2 = 0;b2 < 4;b2++) {
                    ans = max(ans,dp[n][a1][a2][b1][b2]);
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

当你兴致冲冲地打完代码后,你会发现它MLE了。
为什么?因为这份代码的空间复杂度达到了 $\Theta(256N)$,面对 18 MB 的空间限制无疑会爆炸。
怎么办?我们需要加优化,关于第一维的 $i$,我们发现它只和 $i-1$ 有关,所以我们对于 $i$ 和 $i-1$ 将其对 2 取模,结果不会受到影响。

最后的 AC 代码如下:

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 100009;

int f[2][4][4][4][4];
char s[N];
int a[N],ans,n;

int turn(char ch) {
    if(ch == 'M') return 1;
    if(ch == 'F') return 2;
    if(ch == 'B') return 3;
}

int calc(int nw,int i,int j) {
    int cnt = 1;
    if(nw && nw != i && nw != j) cnt++;
    if(i && i != j) cnt++;
    return cnt;
}

int main() {
    scanf("%d",&n);
    scanf("%s",s + 1);
    for(int i = 1;i <= n;i++) {
        a[i] = turn(s[i]);
    }
    memset(f,-1,sizeof(f));
    f[0][0][0][0][0] = 0;
    for(int i = 1;i <= n;i++) {
        for(int a1 = 0;a1 < 4;a1++) {
            for(int b1 = 0;b1 < 4;b1++) {
                for(int a2 = 0;a2 < 4;a2++) {
                    for(int b2 = 0;b2 < 4;b2++) {
                        if(f[(i - 1) % 2][a1][b1][a2][b2] == -1) continue;
                        int tmp1 = f[(i - 1) % 2][a1][b1][a2][b2] + calc(a1,b1,a[i]);
                        int tmp2 = f[(i - 1) % 2][a1][b1][a2][b2] + calc(a2,b2,a[i]);
                        f[i % 2][b1][a[i]][a2][b2] = max(f[i % 2][b1][a[i]][a2][b2],tmp1);
                        f[i % 2][a1][b1][b2][a[i]] = max(f[i % 2][a1][b1][b2][a[i]],tmp2);
                    }
                }
            }
        }
    }
    for(int a1 = 0;a1 < 4;a1++) {
        for(int b1 = 0;b1 < 4;b1++) {
            for(int a2 = 0;a2 < 4;a2++) {
                for(int b2 = 0;b2 < 4;b2++) {
                    ans = max(ans,f[n % 2][a1][b1][a2][b2]);
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}