題目： UVa - 10912 - Simple Minded Hashing

題目說明

26 個英文字母，依序從 1 開始編號，a = 1, b = 2, …, z = 26。

給兩個整數 L、S，求使用 L 個英文字母，組成編號總和為 S 的嚴格遞增字串的字串個數。

Input： 每組測資有兩個整數，依序為 L、S。若皆為 0 表結束。

Output： 輸出使用 L 個英文字母，組成編號總和為 S 的嚴格遞增字串的字串個數。

解題思路

動態規劃題，由於測資範圍不大，因此先算出所有情況的答案再輸出即可。

由於組成的字串必須是嚴格遞增，因此最多只會有 26 個字母，且編號總和最大為 351 ( 1 + 2 + … + 26 )。

定義 dp[i][j][k] 表只使用前 i 個字母 ( 編號 1 ~ i 的字母 )，組成長度為 j，總和為 k 的字串的所有情況數，先設定初始狀態 dp[n][1][n] = 1，對於所有 1 <= n <= 26，因為若只有一個字母，組成與自己編號總和相同的字串，必定就是只有自己一種情況而已。

對於 dp[i][j][k]：

  • 若 k < i，表示 i 無法出現在字串中，則 dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j][k])。
  • 若 k >= i，表示 i 可以出現在字串中，則 dp[i][j][k] += dp[i - 1][j - 1][k - i]，可以理解為若要將 i 放入字串中，可能數為 最大可能字母為 i - 1，長度為 j - 1，總和為 k - i 的字串，因為將 i 接上後會組成 最大可能字母為 i，長度為 j，總和為 k 的字串。

簡單來說，就是不斷枚舉是否能將字母放入最後一位，若無法則至少情況數會是 i - 1 的情況數，這樣才符合最初 dp 數組的定義。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/f8d2Lx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int Cas;
int L, S;
int dp[27][27][352]; // dp[i][j][k] 表只使用前 i 個字母，組成長度為 j，總和為 k 的字串的所有情況數

void compute()
{
    for (int i = 1; i <= 26; ++i) dp[i][1][i] = 1;
    for (int i = 1; i <= 26; ++i) for (int j = 1; j <= i; ++j)
    {
        for (int k = 1; k <= 351; ++k)
        {
            dp[i][j][k] += dp[i - 1][j][k];
            // 判斷是否能將 i 接上
            if (k >= i) dp[i][j][k] += dp[i - 1][j - 1][k - i];
        }
    }
}

int main()
{
    compute();
    while (cin >> L >> S && L && S)
    {
        cout << "Case " << ++Cas << ": ";
        // 由於嚴格遞增，因此最多 26 個字母，S 最大為 351
        if (L > 26 || S > 351) cout << "0\n";
        else cout << dp[26][L][S] << '\n';
    }
}

由於只需要使用 26 個字母的情況，所以可以縮一維。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

const int INF = (int)1e9;

int L, S;
int C;
int dp[27][352];

void compute()
{
    dp[0][0] = 1;
    FOR(i, 1, 27) for (int j = 26; j > 0; --j) FOR(k, i, 352)
        dp[j][k] += dp[j - 1][k - i];
}

int main()
{
    compute();
    while (cin >> L >> S && (L || S))
    {
        cout << "Case " << ++C << ": ";
        if (L > 27 || S > 351) cout << "0\n";
        else cout << dp[L][S] << '\n';
    }
}

參考資料

UVa/10912 - Simple Minded Hashing.cpp at master · morris821028/UVa