【链接】

【题意】

在这里输入题意

【题解】

Swap操作显然只能对(i-1,i)执行才有用。

不然直接将i翻转以及j翻转 显然比直接交换更优。

那么现在我们就相当于有两种操作。

1.将i翻转

2.将i与i-1交换

可以写个DP。

设dp[i]表示1..i都已经满足s1[i]==s2[i]的最小花费

如果s1[i]==s2[i]

dp[i] = dp[i-1]

否则dp[i]=dp[i-1]+1

如果s1[i]!=s1[i-1]并且swap(s1[i],s1[i-1])之后s1[i]==s2[i],s1[i-1]==s2[i-1]

那么dp[i] = min(dp[i],dp[i-2]+1);

cout<<dp[n]<<endl;

【代码】

#include 
    
     #define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define all(x) x.begin(),x.end()#define pb push_back#define lson l,mid,rt<<1#define ri(x) scanf("%d",&x)#define rl(x) scanf("%lld",&x)#define rs(x) scanf("%s",x)#define rson mid+1,r,rt<<1|1using namespace std;const double pi = acos(-1);const int dx[4] = {0,0,1,-1};const int dy[4] = {1,-1,0,0};const int N = 1e6;int n;char s1[N+10],s2[N+10];int dp[N+10];int main(){    #ifdef LOCAL_DEFINE        freopen("rush_in.txt", "r", stdin);    #endif    scanf("%d",&n);    scanf("%s",s1);    scanf("%s",s2);    dp[0] = 0;    rep1(i,1,n){        if (s1[i-1]==s2[i-1]){            dp[i] = dp[i-1]+0;        }else{            dp[i] = dp[i-1]+1;        }        if (i>=2 && s1[i-1]!=s1[i-2] && s1[i-1]==s2[i-2] && s1[i-2]==s2[i-1]){            dp[i] = min(dp[i],dp[i-2]+1);        }    }    printf("%d\n",dp[n]);    return 0;}