洛谷P1385 密令题解动态规划

题目链接：https://www.luogu.com.cn/problem/P1385

题目大意：

给定一小写字母串s，每次操作你可以选择一个p(1<=p<|s|)执行下述修改中的任意一个：

将s[p]改为其字典序+1的字母，将s[p+1]改为其字典序-1的字母

或
将s[p]改为其字典序-1的字母，将s[p+1]改为其字典序+1的字母

在经过任意多次操作后，串s能变化成多少种字符串？

修改过程中必须保证s是合法的小写字母串（即不能对字母‘a’进行字典序-1的操作），答案对1000000007(10^9 + 7)取模。

解题思路：

这里说的字典序（其实就是ASCII码），

对于一个字符串，可以执行的上述 2 种操作都不会更改字符串中所有字符的 ASCII 码总和，所以我们可以定义状态 \(f[i][j]\) 表示前 \(i\) 个字符中的 ASCII码总和为 \(j\) 的情况下的方案数，则可以得到状态转移方程为：

对于所有的 \(i == 1\) （假设字符串坐标从 1 开始），

\(f[1][j] = 1\) （\(0 \le j \lt 26\)）；
对于所有 \(i \lt 1\) ，

\(f[i][j] = \sum_{k=0}^{\min(25,j)} f[i-1][j-k]\)

那么给我们一个字符串 s ，我们只需要知道其长度 n 以及 ASCII码之和（因为都是小写字母，所以都减去字符 'a' 的 ASCII 码），即令一个变量 sum = \(\sum_{i=1}^{n} s[i] - 'a'\) （假设字符串坐标从 1 开始），则总的方案数为 \(f[n][sum]\) ，但是题目问的是合法的转换，那么也就是说原始的字符串不在考虑之内，所以最终的答案还要减1。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 1000000007LL;

long long f[101][2610];

string s;

int T, n, sum;

void init() {

    for (int i = 0; i < 26; i ++) f[1][i] = 1;

    for (int i = 2; i <= 100; i ++)

        for (int j = 0; j < i*26; j ++)

            for (int k = 0; k < 26 && j-k >= 0; k ++)

                f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD;

}

int main() {

    init();

    cin >> T;

    while (T --) {

        cin >> s;

        n = s.length();

        sum = 0;

        for (int i = 0; i < n; i ++) sum += s[i] - 'a';

        cout << (f[n][sum] - 1 + MOD) % MOD << endl;

    }

    return 0;

}

巴特西

洛谷P1385 密令题解动态规划

最新文章

热门文章

巴特西

洛谷P1385 密令 题解 动态规划

最新文章

热门文章

洛谷P1385 密令题解动态规划