CF 1363 F. Rotating Substrings 문자열 일치 DP

문자열은 DP 일반 형식과 일치합니다: dp[i][j], s 전 i 문자, t 전 j 문자와 일치하며 최소 대가를 지불합니다.
이 문제에 대해서는먼저 관찰 조작: [l,r] 구간을 뒤로 옮기면 처리하기 어려워서 s[r]를 s[l]의 앞쪽으로 옮긴다.
여러 차례의 조작을 거쳐 최종적으로 s와 t가 같다.
분명히 매번 조작은 접미사를 조정하기 위해서 s, t의 접미사를 동일하게 한다.
편의를 위해서, 우리는 먼저 s, t 문자열을 뒤집는다.조작이 문자를 뒤로 이동하는 것으로 바뀌었다.([l,r] 조작 표시: 먼저 s[l]를 삭제한 다음에 r 뒤에 삽입)
dp[i][j]는 s전 i자 문자를 나타내고 t의 전 j자 문자와 완전히 일치한다. (그 중에서 s전 i자 중 많은 문자는 모두 삭제한다. (작업 [i,k]를 실행하고 먼저 삭제하고 나중에 필요할 때 대가 없이 삽입할 수 있다)
그러면 이동이 있습니다.
dp[i][j]=min(dp[i][j],dp[i-1][j]+1);//s 전 i-1은 t의 j 접두사 문자를 모을 수 있다.우리는 s[i]를 제거하기만 하면 dp[i][j]=min(dp[i][j], dp[i][j-1]);//앞의 i 문자는 t의 앞 j-1 접두사 문자로 모을 수 있다.우리는 s 전 i 문자에서 삭제된 문자 중에서 t[j]를 선택한 다음 끝에 삽입하면 된다. if(s[i]==t[j])dp[i][j]=min(dp[i][j],dp[i-1][j-1]);//s[i]와 s[j]를 직접 일치시키기

#include 
using namespace std;
typedef long long ll;
const int M = 2e3+7;
char s[M],t[M];
int ps[M][27],pt[M][27];
int dp[M][M];// s   i   ，    t   j      s i       （       ，          ） 
bool ck(int i,int j)
{
	for(int k=0;k<26;k++)
	{
	//	cout<>T;
	while(T--)
	{
		memset(ps,0,sizeof(ps));
		memset(pt,0,sizeof(pt));
		int n;
		cin>>n;
		cin>>(s+1)>>(t+1);
		int i=1;
		while(i)
		{
			int j=n-i+1;
			if(i>j)break;
			swap(s[i],s[j]);
			swap(t[i],t[j]);
			i++;
		}
		memset(dp,0x3f,sizeof(dp));
		dp[0][0]=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<26;j++)
				ps[i][j]=ps[i-1][j],pt[i][j]=pt[i-1][j];
			ps[i][s[i]-'a']++;
			pt[i][t[i]-'a']++;
			dp[i][0]=i;
		}
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(!ck(i,j))continue;//  s i      t j   
			dp[i][j]=min(dp[i][j],dp[i-1][j]+1);// s[i]      ，         
			dp[i][j]=min(dp[i][j],dp[i][j-1]);//  s  i         ，           ，    t[j]
			if(s[i]==t[j])dp[i][j]=min(dp[i][j],dp[i-1][j-1]);//   s[i] s[j]    
		//	cout<1e5)cout<