【題解】Codeforces 1363F. Rotating Substrings

#include <iostream>
#include <algorithm>
using namespace std;
 
int T, n, dp[2005][2005], suf_s[2005][26], suf_t[2005][26];
string s, t;
 
bool check(string x, string y){
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    return x == y;
}
int solve(int x, int y){
    if (x < 0) return 0;
    if (dp[x][y] != -1) return dp[x][y];
    dp[x][y] = solve(x-1, y)+1;
    if (s[x] == t[y]) dp[x][y] = min(dp[x][y], solve(x-1, y-1));
    if (suf_s[x+1][t[y]-'a'] > suf_t[y+1][t[y]-'a']) dp[x][y] = min(dp[x][y], solve(x, y-1));
    return dp[x][y];
}
 
int main() {
    cin >> T;
    while (T--){
        cin >> n;
        cin >> s >> t;
        if (!check(s, t)){
            cout << -1 << "\n";
            continue;
        }
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= n; j++){
                dp[i][j] = -1;
            }
            for (int j = 0; j < 26; j++){
                suf_s[i][j] = 0;
                suf_t[i][j] = 0;
            }
        }
        for (int i = n-1; i >= 0; i--){
            for (int j = 0; j < 26; j++){
                suf_s[i][j] = suf_s[i+1][j];
                suf_t[i][j] = suf_t[i+1][j];
            }
            suf_s[i][s[i]-'a']++;
            suf_t[i][t[i]-'a']++;
        }
        cout << solve(n-1, n-1) << "\n";
    }
}