SP394 ACODE - Alphacode 题解

题目传送门

题意简述

划分数字串 \(S\) ，要求划分后的每个数小于等于 \(26\)（不含前导 \(0\)，且不能拆分为单独一个 \(0\) ），求划分方案数。

\(\texttt{SOLUTION}\)

对于这种方案数类的问题，很容易想到用 dp 来解决。

思考状态？

记数字串的第 \(i\) 个数字为 \(S_i\) 。

不难想到：用 \(dp_i\) 表示 \(S_i\sim S_{len}\) 的划分方案数。

初值？

• 当 \(S_{len}\ne 0\) 时， \(dp_{len}=1\)，显然 \(S_{len}\sim S_{len}\) 只有 \(1\) 种方案，即为单独将 \(S_{len}\) 划分为一段。

• 当 \(S_{len}= 0\) 时， \(dp_{len}=0\)，因为这样无法划分。

转移？

\(dp_i=dp_{i+1}(S_i\text{单独划分为一段})+dp_{i+2}(\overline{S_iS_{i+1}}\text{划分为一段})\)。

当然 \(\overline{S_iS_{i+1}}\le 26\) 时，才能将 \(S_i\) 和 \(S_{i+1}\) 划分为一段，即加上 \(\ dp_{i+2}\)。

然而这里还需要特判，当 \(S_i=0\) 时 \(dp_i=0\) ，因为题面要求划分出的数不含前导 \(0\) ，也不能单独将 \(0\) 划分为一段。

最终答案？

\(dp_{1}\)

\(\texttt{AC CODE}\)

#include
#define IN inline
using namespace std;
const int N=1000010;
int len;
long long dp[N];
char S[N];
int main()
{
	while(scanf("%s",S+1)&&S[1]!='0')
	{
		len=strlen(S+1);
		if(S[len]=='0') dp[len]=0;
		else dp[len]=1;
		dp[len+1]=1;//这里是为了方便dp[len-1]的转移。 
		for(int i=len-1;i>=1;--i)
		{
			dp[i]=dp[i+1];
			if(S[i]=='1'||(S[i]=='2'&&S[i+1]<='6')) dp[i]+=dp[i+2];
			if(S[i]=='0') dp[i]=0;
		}
		printf("%lld\n",dp[1]);
	}
    return 0;
}

欢迎大家指出我的错误，会改的。