Codeforces 156C (DP)

[TOC]

@(K ACMer) by 題解工廠

題意:

給你一個小寫字母構成的序列,序列内支援相鄰的字元進行ASCII碼遷移操作(即一個ASCII碼加x,另一個就減x).問該序列可以變換為多少種其它不同的序列.

分析:

典型的種類計數問題,容易想到要用DP.但是直接想是不容易想到的.需要觀察遷移操作的特點是整個序列的ASCII碼始終是不變的.

定義:dp[i][j]為長度為i,ASCII值為j的序列的種數.

那麼不難想到:

dp[i][j]=∑k=1....26dp[i−1][j−k]

(這裡假設多加的這一位可能是從A到Z的字元)

Code:

#include <bits/stdc++.h>
using namespace std;
const int INF = , M = (int)( + );
const int mod = ;
int dp[][];

int main(void)
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    for (int i = ; i <= ; i++) dp[][i] = ;
    for (int i = ; i <= ; i++) {
        for (int j = i; j <=  * i; j++) {
            for (int k = max(, j - ); k <= j - ; k++) {
                dp[i][j] = (dp[i][j] + dp[i - ][k]) % mod;
            }
        }
    }
    string s;
    while (t--) {
        cin >> s;
        int sum = ;
        for (int i = ; i < s.size(); i++) sum += s[i] - 'a' + ;
        cout << (dp[s.size()][sum] - ) % mod<< endl;
    }
    return ;
}