自动搬运

查看原文

来自洛谷，原作者为

	NKU_AI_HMX New start......

搬运于2025-08-24 21:50:10，当前版本为作者最后更新于2021-02-03 02:36:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

目录

1. 思路简述

2. 状态转移方程

3. 如何优化

4. 最终代码

正文

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);

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

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

第二种代码

1. $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;
		}

$f[i][0]=f[i-1][0]$ 没什么好说的，非常正确，没有争议。$f[i][1]$ 就有点问题了，按上面的代码就有两个转移途径，如果 $num[i-1]==1$，先让自己加上 $num[i-1]$ 是 $1$，自己变成 $0$，然后考虑到数列单调性，再通过前面的加的操作让第 $i-1$ 个数符合单调法则变成 $-1$ 或者 $0$，第二种转移就 $num[i-1]\ne1$ 要让第 $i$ 个数等于 $0$，就需要先让前一个数变成 $1$，然而它变成 $1$ 后数列又不单调，于是乎我目前看到的所有题解（如果说错那我没看到，不好意思）都得出来一个看似显而易见的结论 $f[i][1]=INF$ 但是我在这里要说这个结论是错的。

大家看这样一个数列 $-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$ 呢？以上就说明了第二种代码的第一个判断的多余之处。

2. $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]$ 的那一行参照上面的说法也比较冗长可以改进为第一种代码。

3. $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;
}

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