自动搬运

查看原文

来自洛谷，原作者为

	jyz666 原来这就是AFOed

搬运于2025-08-24 22:16:03，当前版本为作者最后更新于2020-10-20 20:48:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题解 P5965 【[PA2019]A+B】

传送门

退役题解...

去冲文化课了。（泪目）

感谢巨佬帮我调的 $\LaTeX$

简单数位 DP，令 f[i]表示到第i位的方案数。

那么转移非常显然：

1. 第i位由一对数字加出

2. 第i位和第i-1位一起由一对数字加出

即

$$\begin{cases} f \lbrack i \rbrack = f \lbrack i-1 \rbrack \times (a \lbrack i \rbrack + 1) & \text { if $ a \lbrack i-1 \rbrack \neq 1 $} \\ f \lbrack i \rbrack = f \lbrack i-1 \rbrack \times (a \lbrack i \rbrack + 1) + f \lbrack i-2 \rbrack \times (9 - a \lbrack i \rbrack) & \text { if $ a \lbrack i-1 \rbrack = 1 $} \end{cases} $$

直接计算即可。

上代码》》

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
inline void read(int &x) {
    int f = 1; x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}
const int maxn=25;
int len,a[maxn];
string s;
ll f[maxn];
int main(){
	cin>>s;
	len=s.size();
	for(int i=1;i<=len;i++)
		a[i]=s[i-1]-'0';
	f[0]=1;
	for(int i=1;i<=len;i++){
		f[i]=f[i-1]*(a[i]+1);
		if(i>=2&&a[i-1]==1)
			f[i]+=f[i-2]*(9-a[i]);
	}
	printf("%lld",f[len]);
	return 0;
}

谢谢大家，谢谢$Luogu$,再见。