题解 P5965 【[PA2019]A+B】

· · 题解

题解 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,再见。