USACO07OPEN Cheapest Palindrome

题目传送门

最近做了好多“奶牛题”

---

好不容易把转移方程想出来了，却不会转移顺序

f[l][r] = min(f[l+1][r] + cost[l], f[l][r-1] + cost[r])

看了看某位(dalao)的博客，发现用记搜比较容易转移

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define LL long long
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
      k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int cost[30], f[2010][2010];
char s[2010];
int dp(int l, int r) {
    if(l > r) return f[l][r] = 0;
    if(f[l][r] != -1) return f[l][r];
    if(s[l] == s[r]) f[l][r] = dp(l+1, r-1);
    else f[l][r] = min(dp(l+1, r) + cost[s[l]], dp(l, r-1) + cost[s[r]]);
    return f[l][r];
}
int main() {
    int n = read(), m = read();
    scanf("%s", s+1);
    memset(f, -1, sizeof(f));
    for(int i = 1; i <= n; ++i) {
        char c; cin >> c;
        cost[c] = min(read(), read());
    }
    cout << dp(1, m);
    return 0;
}