[UVA][DP] 10912 - Simple Minded Hashing
| 4th IIUC Inter-University Programming Contest, 2005 |
|
| H |
Simple Minded Hashing |
| Input: standard input |
|
| Problemsetter: Sohel Hafiz |
|
All of you know a bit or two about hashing. It involves mapping an element into a numerical value using some mathematical function. In this problem we will consider a very ‘simple minded hashing’. It involves assigning numerical value to the alphabets and summing these values of the characters.
For example, the string “acm” is mapped to 1 + 3 + 13 = 17. Unfortunately, this method does not give one-to-one mapping. The string “adl” also maps to 17 (1 + 4 + 12). This is called collision.
In this problem you will have to find the number of strings of length L, which maps to an integer S, using the above hash function. You have to consider strings that have only lowercase letters in strictly ascending order.
Suppose L = 3 and S = 10, there are 4 such strings.
- abg
- acf
- ade
- bce
agb also produces 10 but the letters are not strictly in ascending order.
bh also produces 10 but it has 2 letters.
Input
There will be several cases. Each case consists of 2 integers L and S. (0 < L, S < 10000). Input is terminated with 2 zeros.
Output
For each case, output Case #: where # is replaced by case number. Then output the result. Follow the sample for exact format. The result will fit in 32 bit signed integers.
| Sample Input |
Output for Sample Input |
| 3 10 |
Case 1: 4 |
逐一增加字母, 數據給的範圍其實是騙人的, 根本不會那麼大, 都已經嚴格遞增的小寫字母, 因此不會超過 26 個
#include <stdio.h>
#include <string.h>
int DP[27][27][352];/*[letter][length][sum]*/
void build() {
int i, j, k;
memset(DP, 0, sizeof(DP));
DP[0][0][0] = 1;
for(i = 1; i <= 26; i++) {
for(j = 0; j <= i; j++) {
for(k = 0; k < 352; k++) {
DP[i][j][k] = DP[i-1][j][k];
if(j > 0 && k >= i)
DP[i][j][k] += DP[i-1][j-1][k-i];
}
}
}
}
int main() {
build();
int L, S, Case = 0;
while(scanf("%d %d", &L, &S) == 2) {
if(L == 0 && S == 0)
break;
printf("Case %d: ", ++Case);
if(L > 26 || S > 351)
puts("0");
else
printf("%d\n", DP[26][L][S]);
}
return 0;
}
可以稍微解釋最佳子結構嗎?
為什麼dp[i][j][k]要先等於dp[i-1][j][k]呢??
由於 dp[i][j][k] 的定義是使用 <= i('a'-'z') 去構成長度為 j 且總和為 k 的方法數。
那麼可以從 dp[i][j][k] += dp[i-1][j][k]
這是一個其中的子結構。 2013-05-25 20:23:21