Codeforces Round #646(Div.2) F Rotating Substrings(사고 DP)
1641 단어 Codeforces 문제집동적 기획의 사고 DP
#include
using namespace std;
#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=2e3+10;
const int maxm=5e5+10;
const ll INF=1e18;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){
if(y==0) return x;
return gcd(y,x%y);
}
/*
:
DP , ,
, DP 。
, 。
, ,
, , ,
a b , 。
*/
int t,n;
string a,b;
int dp[maxn][maxn];
int cnt1[maxn][26],cnt2[maxn][26];
int judge(string x,string y){
sort(x.begin(),x.end());
sort(y.begin(),y.end());
return x==y;
}
int main(){
ios::sync_with_stdio(false);/*
freopen("d://in.txt","r",stdin);
freopen("d://out.txt","w",stdout);*/
cin>>t;
while(t--){
cin>>n>>a>>b;
if(!judge(a,b)) {cout<=1;i--){
rep(j,0,26){
cnt1[i][j]=cnt1[i+1][j];
cnt2[i][j]=cnt2[i+1][j];
}
cnt1[i][a[i]-'a']++;
cnt2[i][b[i]-'a']++;
}
rep(i,0,n+1) dp[0][i]=dp[i][0]=0;
rep(i,1,n+1) rep(j,1,n+1){
dp[i][j]=dp[i-1][j];
dp[i][j]=max(dp[i][j],dp[i][j-1]);
if(a[i]==b[j]){
int flg=1;
rep(k,0,26) if(cnt1[i][k]