题解 P3558 【[POI2013]BAJ-Bytecomputer】

NKU_AI_HMX · 2021-02-03 02:36:50 · 题解

这篇题解主要是对其他题解做出补充和优化，解决大家的一些问题，帮助大家理解。

正文

1. 思路简述

动态规划或者贪心，记忆搜索都可，其他题解都有说明，这里我主要说动态规划，我们构造函数 f[j][i]，其表示前 j 个数以 i(i=-1,0,1) 结尾的最少改变次数。如果大家可以想到这个方程那么已经迈出一大步了，接下来就是怎么转移状态。

2. 状态转移

我先放出两种代码

memset(f, 63, sizeof(f));
    f[1][a[1] + 1] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] == -1)
        {
            f[i][0] = f[i - 1][0];
            f[i][2] = f[i - 1][2] + 2;
        }
        if (a[i] == 0)
        {
            f[i][0] = f[i - 1][0] + 1;
            f[i][1] = min(f[i - 1][0], f[i - 1][1]);
            f[i][2] = f[i - 1][2] + 1;
        }
        if (a[i] == 1)
        {
            f[i][0] = f[i - 1][0] + 2;
            f[i][1] = f[i - 1][0] + 1;
            f[i][2] = min(f[i - 1][0], min(f[i - 1][1], f[i - 1][2]));
        }
    }
    int temp = min(f[n][0], min(f[n][1], f[n][2]));
    if (temp >= inf)cout << "BRAK";
    else cout << temp;

f[1][0]=INF,f[1][1]=INF,f[1][2]=INF;
    f[1][num[1]+1]=0;
    for(register int i=2;i<=n;i++)
    {
        if(num[i]==-1)
        {
            f[i][0]=f[i-1][0];
            f[i][1]=(num[i-1]==1)?min(f[i-1][0],f[i-1][1])+1:INF;
            f[i][2]=(num[i-1]==1)?min(f[i-1][0],min(f[i-1][1],f[i-1][2]))+2:f[i-1][2]+2;
        }
        if(num[i]==0)
        {
            f[i][0]=f[i-1][0]+1;
            f[i][1]=min(f[i-1][0],f[i-1][1]);
            f[i][2]=(num[i-1]==1)?min(f[i-1][0],min(f[i-1][1],f[i-1][2]))+1:f[i-1][2]+1;
        }
        if(num[i]==1)
        {
            f[i][0]=f[i-1][0]+2;
            f[i][1]=(num[i-1]==-1)?min(f[i-1][0],f[i-1][1])+1:f[i-1][0]+1;
            f[i][2]=min(f[i-1][0],min(f[i-1][1],f[i-1][2]));
        }
    }
    int ans=min(f[n][0],min(f[n][1],f[n][2]));
    if(ans>=INF) printf("BRAK\n");
    else printf("%d\n",ans);

大家如果看了其他的题解就会发现有两种代码，第一种，转移函数十分简要，而且题解也没说明，没有第二种考虑周全，而第二种的转移函数似乎又显得十分冗长，又有些多余。

接下来我给大家解释一下其中的道理，并指出其他题解没说明白的或者说错误的地方。

第二种代码

num[i]==-1

if(num[i]==-1)
    {
        f[i][0]=f[i-1][0];
        f[i][1]=(num[i-1]==1)?min(f[i-1][0],f[i-1][1])+1:INF;
        f[i][2]=(num[i-1]==1)?min(f[i-1][0],min(f[i-1][1],f[i-1][2]))+2:f[i-1][2]+2;
    }

大家看这样一个数列 $-1,1,0,-1$ 按照上面的算法$f[4][1]=INF$ 但是呢？看下面（我每次只操作一个数）： $-1,1,0,-1$ $\to$ $-1,1,1,-1$ $\to$ $-1,1,1,0$ $\to$ $-1,0,1,0$ $\to$ $-1,-1,1,0$ $\to$ $-1,-1,0,0

啊？转移过去了？奇怪吧？其实不奇怪，上面讲的第一种代码根本没管多次来回操作的问题(就这题而言不需要管)。而第二种代码他管了，甚至它自己都不知道它管了，因为只管了一部分，而上面说的那个 INF 就没管，那它管了哪部分呢？前面那部分。如果 num[i-1]==1 他先让第 i 个数加了第 i-1 个数之后再通过前面的数去改变了第 i-1 个数，但是后面 num[i-1]\ne1 却忘了这一点，不过还好忘了，不然很难写下去了。接下来我来说一下为什么这两种代码都可以过，以及为什么不用考虑来回多次操作的问题。

如果你需要用前面一个数去改变后面一个数，而这个数本身是具有改变后面数的能力的，增加或者减少，如果是增加，当你用 1，去增加后面的数时你把他增加到 0 或者 1，目的就是为了让数列递增，如果增加到 0，你完全是为了让前面一段递增，因为 0 不会对后面的数的改变有任何作用，反而会提升数列的高度，所以对后面的数是没益处的。然后你又用前面的 -1 让 1 符合递增序列的要求，那么这就脱裤子放屁了，你可以直接用前面的 -1 把 1 降到 -1 而不用让 1 去把后面的 -1变成 0，而变成 0的这个解我们就认为它一定不会是唯一的一个最优解直接给 INF 就好了。这就对应了上面循环的 f[i][1] 的操作，而 INF 并不代表他不可转移，只是一定不是唯一的最优，不取它而已。（不用怕因为我们给可转移的情况赋值 INF 而在最后错误判断情况为不可转移，为什么大家自己思考一下应该可以出来，想出不来欢迎评论区留言）

同样，当我们用 1 把后面一个数变成 1 的时候也没必要回过头去再把 1 给降低，因为它后面都是 1 了它为啥还要变成 0 或者 -1 呢？以上就说明了第二种代码的第一个判断的多余之处。

num[i]==0

if(num[i]==0)
    {
        f[i][0]=f[i-1][0]+1;
        f[i][1]=min(f[i-1][0],f[i-1][1]);
        f[i][2]=(num[i-1]==1)?min(f[i-1][0],min(f[i-1][1],f[i-1][2]))+1:f[i-1][2]+1;
    }

同理这里面 f[i][2] 的那一行参照上面的说法也比较冗长可以改进为第一种代码。

num[i]==1

if(num[i]==1)
    {
        f[i][0]=f[i-1][0]+2;
        f[i][1]=(num[i-1]==-1)?min(f[i-1][0],f[i-1][1])+1:f[i-1][0]+1;
        f[i][2]=min(f[i-1][0],min(f[i-1][1],f[i-1][2]));
    }

现在我们考虑前面一个数让后面减小的情况,两种选择，减到 -1 或者减到 0。

减到 -1 很好理解，这里不叙述了。

如果减到 0，那就没必要再把前面的 -1 加到 0 因为你必然是用更前面的 1 把 -1 加到 0，而这个 1，是不符合递增要求的，你就又得用更更前面的 -1 把他减掉，最后形成前面全是 -1 和 0 的局面，而你如果又是这样往复多次操作的话，参照上面几段，你又脱裤子放屁了。
用 -1 把后面的数减到 0，然后再用前面的数把 -1 加到 0。大家仔细想想，是不是多此一举了，你既然要把 -1 加到 0是不是说明前面全是 0 或者 -1，你为了保证数列递增而这样操作的，对吧。那你用来把 -1 加到 0 的那个 1 哪里来的？哟！我可以先用那个 1 把后面的数加上去再用更前面的 -1 把那个 1 再减回来，这样就只剩 0,-1 了。我们叫这种行为叫脱裤子放屁。大哥，既然前面有 -1 你为啥要让把后面提升到 0 还费那么大的力？直接用 -1 扫过去让他都变成 -1不就好了，那我第 i-1 个数还用动吗？他就是 -1 嘛。

以上就说明了第二种代码一些转移的多余，精简代码看第一种。

3. 如何优化

第一，~~我们可以滚~~。我的意思是滚动数组，滚到只用开 f[3] 和一些临时变量，注意滚动的时候要调整每一种情况下函数的递推顺序，不然就会造成历史数据丢失。

4. 最终代码

#include<bits/stdc++.h>
#define ll long long
#define re register
#define pf putchar(' ')
#define pfn putchar('\n')
using namespace std;
char ch1;
template<class T>
inline void rd(T& x) {
    x = 0; bool w = 0;
    ch1 = getchar();
    while (!isdigit(ch1)) { ch1 == '-' && (w = 1), ch1 = getchar(); }
    while (isdigit(ch1)) { x = (x << 1) + (x << 3) + (ch1 & 15), ch1 = getchar(); }
    w && (x = (~x) + 1);
}
template<class T>
inline void wr(T x)
{
    if (x < 0) x = -x, putchar('-');
    if (x < 10) {
        putchar(x + 48);
        return;
    }
    T L = x / 10;
    wr(L);
    putchar(x - ((L << 1) + (L << 3)) + 48);
}
int n,x,f[3]; 
int inf = 1 << 27;
int main()
{
    rd(n); rd(x);
    memset(f, 63, sizeof(f));
    f[x + 1] = 0;
    for (re int i = 2; i <= n; i++)
    {
        rd(x);
        if (x == -1)
        {
            f[1] = inf;
            f[2] += 2;
        }
        else if (x == 0)
        {
            f[1] = min(f[0], f[1]);
            f[0]++;
            f[2]++;
        }
        else
        {
            f[2] = min(f[0], min(f[1], f[2]));
            f[1] = f[0] + 1;
            f[0] += 2;
        }
    }
    int temp = min(f[0], min(f[1], f[2]));
    if (temp >= inf)printf("BRAK");
    else wr(temp);
    return 0;
}

(如果有情况未覆盖，参照上面的思路可自行推理)

题解 P3558 【[POI2013]BAJ-Bytecomputer】

目录

正文

1. 思路简述

2. 状态转移

3. 如何优化

4. 最终代码