一个小写字母组成的字符串和允许更改次数k，n组序偶的价值，求能获得的最大价值
定义dp[k][l][i]位更改第k次时长度为l的串末尾为i时的最大收益。分原本字符串末尾就是i和不是两种去递推。
注意初始化问题。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define INF 0x3f3f3f3f 6 using namespace std; 7 typedef long long LL; 8 9 const int maxn = 1e2 + 10; 10 const int maxk = 110; 11 char str[maxn]; 12 int val[30][30]; 13 int N, K; 14 int dp[maxk][maxn][30]; 15 16 int main() { 17 scanf("%s", str); 18 int len = strlen(str); 19 scanf("%d", &K); 20 scanf("%d", &N); 21 char c1, c2; 22 int v; 23 while (N--) { 24 getchar(); 25 scanf("%c %c %d", &c1, &c2, &v); 26 val[c1 - 'a'][c2 - 'a'] = v; 27 } 28 for (int k = 0; k <= K; k++) { 29 for (int l = 0; l <= len; l++) { 30 for (int i = 0; i < 26; i++) { 31 dp[k][l][i] = -INF; 32 } 33 } 34 } 35 for (int i = 0; i < 26; i++) dp[1][1][i] = 0; 36 dp[0][1][str[0] - 'a'] = 0; 37 for (int i = 2; i <= len; i++) { 38 int t1 = str[i - 1] - 'a', t2 = str[i - 2] - 'a'; 39 dp[0][i][t1] = dp[0][i - 1][t2] + val[t2][t1]; 40 } 41 for (int l = 2; l <= len; l++) { 42 for (int k = 1; k <= K; k++) { 43 for (int i = 0; i < 26; i++) { 44 for (int j = 0; j < 26; j++) { 45 if (str[l - 1] - 'a' == j) dp[k][l][j] = max(val[i][j] + dp[k][l - 1][i], dp[k][l][j]); 46 if (dp[k - 1][l - 1][i] == -INF) continue; 47 dp[k][l][j] = max(dp[k][l][j], dp[k - 1][l - 1][i] + val[i][j]); 48 } 49 } 50 } 51 } 52 int ans = -INF; 53 for (int i = 0; i <= K; i++) { 54 for (int j = 0; j < 26; j++) { 55 ans = max(ans, dp[i][len][j]); 56 } 57 58 } 59 printf("%d ", ans); 60 return 0; 61 }