CSUSTOJ 你真的会字符串吗？（DP）

本文主要是介绍CSUSTOJ 你真的会字符串吗？（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：
最后结果每一位都等于$s[i]$，
只要知道当前位的$pre[i]$值和当前位的$t[i]$值就好了。
所以定义$dp[i][j]$为到了第$i$为，$pre[i+1]=j$的方案数。
然后直接枚举当前位和当前$pre[i]$值就可以转移了。

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <queue>using namespace std;typedef unsigned long long ull;
typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 998244353;ll f[maxn][100];
int a[maxn];int main() {int n;scanf("%d",&n);for(int i = n;i >= 1;i--) {scanf("%1d",&a[i]);}for(int i = 0;i <= 9;i++) {if(i * a[1] % 10 == a[1]) f[1][a[1] * i / 10]++;}for(int i = 2;i <= n;i++) {for(int j = 0;j <= 81;j++) { //pre[i]的值for(int k = 0;k <= 9;k++) {int num = j + k * a[i];if(num % 10 == a[i]) {int pre_now = (a[i] * k + j) / 10;f[i][pre_now] += f[i - 1][j];f[i][pre_now] %= mod;}}}}ll ans = 0;for(int i = 0;i <= 81;i++) {ans = (ans + f[n][i]) % mod;}printf("%lld\n",ans);return 0;
}

这篇关于CSUSTOJ 你真的会字符串吗？（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---