记录编号	604173	评测结果	AAAATTTTTTTTTTTT
题目名称	3321.[USACO19 DEC Gold]Moortal Cowmbat	最终得分	25
用户昵称	LikableP	是否通过	未通过
代码语言	C++	运行时间	24.083 s
提交时间	2025-07-30 14:26:45	内存使用	8.51 MiB

#include <cstdio>
#include <cstring>

template <typename T> T read();
template <typename T> void write(T, char);
void read(char *);

const int MAXN = 1e5 + 10;

int n, m, k;
char str[MAXN];
int sum[MAXN][30];
int a[30][30];
int f[MAXN];

int main() {
  freopen("cowmbat.in", "r", stdin);
  freopen("cowmbat.out", "w", stdout);
  n = read<int>(), m = read<int>(), k = read<int>();
  read(str + 1);
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= m; ++j) {
      a[i][j] = read<int>();
    }
  }

  for (int k = 1; k <= m; ++k) {
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= m; ++j) {
        if (a[i][k] + a[k][j] < a[i][j]) {
          a[i][j] = a[i][k] + a[k][j];
        }
      }
    }
  }

  fprintf(stderr, "\033[0m\033[1;32m");
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= m; ++j) {
      fprintf(stderr, "%d%c", a[i][j], " \n"[j == m]);
    }
  }
  fprintf(stderr, "\033[0m");

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (str[i] - 'a' == j - 1)
        sum[i][j] = sum[i - 1][j];
      else
        sum[i][j] = sum[i - 1][j] + a[str[i] - 'a' + 1][j];
    }
  }

  fprintf(stderr, "\033[0m\033[1;32m");
  for (int i = 1; i <= m; ++i) {
    fprintf(stderr, "char : %c:", i - 1 + 'a');
    for (int j = 1; j <= n; ++j) {
      fprintf(stderr, "%d%c", sum[j][i], " \n"[j == n]);
    }
  }
  fprintf(stderr, "\033[0m");

  memset(f, 0x3f, sizeof f);
  f[0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= i - k; ++j) {
      for (int c = 1; c <= m; ++c) {
        if (f[j] + sum[i][c] - sum[j][c] < f[i]) {
          f[i] = f[j] + sum[i][c] - sum[j][c];
        }
      }
    }
  }

  fprintf(stderr, "\033[0m\033[1;32m");
  for (int i = 1; i <= n; ++i) {
    fprintf(stderr, "%d%c", f[i], " \n"[i == n]);
  }
  fprintf(stderr, "\033[0m");

  write(f[n], '\n');
  return 0;
}

#define isdigit(ch) (ch >= '0' && ch <= '9')
template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}
#undef isdigit

#define isspace(ch) (ch == ' ' || ch == '\n')
void read(char *str) {
  char ch = getchar();
  for (; isspace(ch); ch = getchar());
  for (; !isspace(ch); ch = getchar()) *str++ = ch;
  *str = 0;
}
#undef isspace

template <typename T> void write(T x, char ed) {
  if (x < 0) putchar('-'), x = -x;
  int sta[sizeof(T) << 2], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}