Moortal Cownbat (USACO Gold 2019 December)

此题知识点：N到N最短路（Floyd-Warshall） + DP + prefix sum。

DP构造有难度（主要是K可能很大），直观的想法是：前i个字母中固定最后一个字母和最后一个streak长度。然后会发现这个不太行，因为空间太大了。

正确的DP构造，是不需要streak长度这一维，可以直接在合法的串上做DP，扩展的时候有两种情况：继续现有字母，或者最后正好 $K$ 个字母是 $j$ ，具体见下面代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m, K;
int a[26][26];  // <= 1000
char s[100005];
int dp[100005][26]; // dp[i][j]: cheapest cost of 0..i, last letter is j
const int INF = 1e9;
int ps[26][100005]; // prefix sum of distance
 
int main() {
    scanf("%d %d %d", &n, &m, &K);
    scanf("%s", s);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
 
	// floyd-warshall
	for (int k = 0; k < m; k++)
		for (int i = 0; i < m; i++)
			for (int j = 0; j < m; j++)
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
 
    // prefix sum
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            ps[i][j+1] = ps[i][j] + a[s[j]-'a'][i];
 
    // dp
    for (int i = 0; i < n; i++)
        fill(dp[i], dp[i]+m, INF);
    for (int i = K-1; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (i == K-1) {     // base case
                dp[i][j] = ps[j][i+1] - ps[j][i+1-K];
                continue;
            }
            // continue last letter
            dp[i][j] = dp[i-1][j] + a[s[i]-'a'][j];
            for (int k = 0; k < m; k++) {
                // change from any letter to j exactly K letters ago
                if (k != j)
                    dp[i][j] = min(dp[i][j], dp[i-K][k] + ps[j][i+1] - ps[j][i+1-K]);
            }
        }
 
    int ans = INF;
    for (int i = 0; i < m; i++)
        ans = min(ans, dp[n-1][i]);
    printf("%d", ans);
 
    return 0;
}