[数据结构与算法]AtCoder Beginner Contest 220 D-FG operation(动态规划)

问题描述：

我们有N个0-9的整数($A_1$,·····$A_n$)，从左到右按顺序排列。现在我们有F和G操作，我们将不断地重复选取F或G操作，直到序列的元素数为1。

• F：删除最左边的两个数x和y，然后将(x+y)%10插入序列最左边
• G：删除最左边的两个数x和y，然后将(x*y)%10插入序列最左边

N个数需要N-1次操作才能将其变为长度为1的序列，每次有两种操作可以选择，所以总共会有 $2^{N?1}$种情况，我们要统计最后一个值分别为0-9的操作序列种数。

问题分析：

N为$10^5$数量级，直接暴力肯定超限。说实话这题我一开始见到也没有什么思路。但我发现如果将0-9的每一种结果保存为一种状态，采用动态规划可能会行得通。
我们可以设置一个二维数组dp[N][10]，dp[i][j]代表前i个操作产生结果为j的结果总数。这样我们就可以将每次操作的状态保存下来，以至于当有多次重叠计算状态的时候，我们就不必重复计算，解决了重叠子问题。
初值dp[1][a[1]] = 1，因为当只有一个数的时候，结果状态只能为a[i]。其余初始化为0即可。接下来是转移方程的写法。
假设我们现在已经确定了dp[i][j]，dp[i][j]接下来有两种操作：F操作之后得到dp[i+1][(j + a[i+1])%10]，所以dp[i+1][(j + a[i+1])%10]这个新状态可以由dp[i][j]得到，但新状态不是只能由本次操作得到，可能由之前的某个F或G操作已经得到一个值，所以我们要在新状态的基础上再加上dp[i][j]，G操作同理。
dp[i + 1][(j + a[i + 1]) % 10] = (dp[i][j] + dp[i + 1][(j + a[i + 1]) % 10]) % mod
dp[i + 1][(j * a[i + 1]) % 10] = (dp[i][j] + dp[i + 1][(j * a[i + 1]) % 10]) % mod
最后遍历dp[n][0-9]即可，因为此时dp[n][0-9]就代表经过了n-1次操作产生0-9状态的操作序列种数。
最后上代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 998244353;
const ll maxn = 1e5 + 5;
int dp[maxn][10];
int main()
{
    ios::sync_with_stdio(0);  //提升C++的cin，cout的读写速度
    cin.tie(0);				//我也是刚学到，否则报错
    cout.tie(0);
    ll n;
    vector<ll> a(n);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    memset(dp, 0, sizeof(dp));
    dp[1][a[1]] = 1;
    for (int i = 1; i <= n - 1; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            dp[i + 1][(j + a[i + 1]) % 10] = (dp[i][j] + dp[i + 1][(j + a[i + 1]) % 10]) % N;
            dp[i + 1][(j * a[i + 1]) % 10] = (dp[i][j] + dp[i + 1][(j * a[i + 1]) % 10]) % N;
        }
    }
    for (int k = 0; k < 10; k++)
    {
        cout << dp[n][k] % N << endl;
    }
}

欢迎大家评论区交流~