Codeforces Round #646(Div.2) F Rotating Substrings(사고 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]

좋은 웹페이지 즐겨찾기