14437 준오는 심술쟁이

14437 준오는 심술쟁이 https://www.acmicpc.net/problem/14437

알파벳 소문자로 구성된 문자열중 문자를 골라 바꿀 수 있다.
(문자는 +[1, 25]중 하나로 바꿀 수 있고 이미 바꾼문자를 바꿀순 없음)
바꾼 합이 S가 될때까지 바꾼다. 경우의 수를 구하는 문제다.

일반적인 Top-down 방식으로 짰는데 시간초과가 났다.
계산해보니 $O(NM$*$25)$로 $10^8$이 넘는다.

#include <cstdio> #include <cstring> #define mod 1000000007 int S, N; char str[3001]; int dp[3001][3001]; int solve(int index, int sum) {     if (index == N) {         if (sum == 0) return 1;         else return 0;     }     int &ret = dp[index][sum];     if (ret != -1) return ret;     ret = 0;     for (int next = 0; next <= 25;next++) {         if (sum - next < 0) break;         ret += solve(index + 1, sum - next);         ret %= mod;     }     return ret % mod; } int main() {     memset(dp, -1, sizeof dp);     scanf("%d", &S);     scanf("%s", &str);     N = strlen(str);     printf("%d\n", solve(0, S));     return 0; } Colored by Color Scripter

cs

                         <TLE 코드>

Bottom-up 방식으로 합들을 미리 저장하여 $O(NM)$으로 구할 수 있다.

#include <cstdio> #include <cstring> #define mod 1000000007 #define min(a,b) ((a)<(b)?(a):(b)) int S, N; char str[3001]; int buff[3001]; int dp[3001][3001]; int main() {     scanf("%d", &S);     scanf("%s", &str);     N = strlen(str);     dp[0][0]= 1;     for (int n = 1;n <= N;n++) {         for (int s = 0;s <= S;s++) {             buff[s] = s == 0 ? dp[n - 1][s] % mod: (dp[n - 1][s] % mod + buff[s - 1] % mod) % mod;         }         for (int s = 0;s <= S;s++) {             if (s - 26 >= 0) dp[n][s] = ((buff[s] + mod) - buff[s - 26]) % mod;             else dp[n][s] = buff[s];         }     }     printf("%d\n", dp[N][S]);     return 0; } Colored by Color Scripter

cs