CF404D-DP

正经的东西

题意

给定一个字符串，只包含'0','1','2','*','?'五种字符，其中'?'可被替换为其他任何一种，求使序列符合扫雷地图定义的方案数。

一个数字字符大小表示与之临近的位置总共有多少个雷。

思路

DP。

和其他题解不太相同，我们每个点只记录三种状态：0,1,2，分别表示此点的下一位不为雷、为雷，和本身就是雷的此位以前的方案数。

注意，这些状态除了最后一个，与该点本身为何没有关系。

考虑每一个点分别为何的情况下从上一个位置的什么状态转移：

为0：继承0.
```
f[i][0]+=f[i-1][0]
```
为1：自身0的状态继承上一个为雷的状态，为1的继承为0的。
```
f[i][0]+=f[i-1][2]

f[i][1]++f[i-1][0]
```
为2：只能将自身为1的状态继承上一个为雷的状态。
```
f[i][1]+=f[i-1][2]
```
为雷：继承上一个为1、为雷的状态。
```
f[i][2]+=f[i-1][2]+f[i-1][1]
```

为？：将上述所有状态全部转移。

f[i][0]+=f[i-1][0]+f[i-1][2]

f[i][1]+=f[i-1][0]+f[i-1][2]

f[i][2]+=f[i-1][1]+f[i-1][2]

至于上面转移的原因显然，即每个点后面的点能继承当前点的哪个状态。

注意：初始化f[0][0]=f[0][1]=1，后者是为了计算第一位为雷的情况。此外，所有该点未被转移的状态都为0。

于是我们线性DP求解即可。

不正经的东西

首先，显然上面的第一维可以滚动数组优化。
然后，我们可以边输入边计算，就不用数组存东西啦。这样我们将空间复杂度优化到了\(O(1)\)
最后，你就会发现吾的做法即好想又好写又省时间又省空间

达成成就：内存使用小于代码大小

代码

#include<cstdio>

using namespace std;

const int mod=1e9+7;

int f[2][3];

int x,i;char c;

inline void qm(int &a,const int& b){(a+=b)>=mod?(a-=mod):a;}

int main(){

	c=getchar();

	while(c<=32)c=getchar();

	f[0][0]=f[0][1]=1;

	for(x=1;c>32;x++,c=getchar()){

		i=x&1;

		f[i][0]=f[i][1]=f[i][2]=0;

		switch(c){

			case '0':{

				qm(f[i][0],f[i^1][0]);

				break;

			}

			case '1':{

				qm(f[i][1],f[i^1][0]);

				qm(f[i][0],f[i^1][2]);

				break;

			}

			case '2':{

				qm(f[i][1],f[i^1][2]);

				break;

			}

			case '*':{

				qm(f[i][2],f[i^1][1]+f[i^1][2]);

				break;

			}

			case '?':{

				qm(f[i][0],f[i^1][0]);

				qm(f[i][0],f[i^1][2]);

				qm(f[i][1],f[i^1][0]);

				qm(f[i][1],f[i^1][2]);

				qm(f[i][2],f[i^1][1]);

				qm(f[i][2],f[i^1][2]);

				break;

			}

		}

	}

	x--;

	printf("%d",(f[x&1][0]+f[x&1][2])%mod);

	return 0;

}

巴特西

CF404D-DP【成就达成】

CF404D-DP

正经的东西

题意

思路

不正经的东西

达成成就：内存使用小于代码大小

代码

最新文章

热门文章