寒假打卡——AcWing1208翻硬币

2021-01-20

题目

image.png

题意:
给定两个字符串不妨取第一个字符串为 s,第二个字符串为 t,这些字符串是由硬币组成的,o(小写字母)代表反面,'*'代表正面,可以同时翻转两个相邻的硬币,问最少需要翻动多少次

思路:
一种暴力思路是直接 dfs 搜索,注意剪枝优化即可,另外一种是递推即使定义这样一种状态:
f(x): 前 x 个字符前都是相同的,那么如果第 x 个字符不相同就翻转第 x 个和第 x+1 个即可,同时更新翻转次数,直到倒数第一个便可求出答案,题目保证有解。

代码:

第一种递推
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<vector>
#include<cmath>

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;

    int cnt = 0;
    int len = s.size();
    for (int i = 0; i < len; i++) {
        if (s[i] != t[i]) {
            cnt++;
            if (s[i + 1] == '*') s[i + 1] = 'o';
            else s[i + 1] = '*';
        }
    }
    cout << cnt << '\n';
    return 0;
}


第二种:递归

#include<bits/stdc++.h>

using namespace std;

string t;
int ans;
int len;

void swap(char &p,char &q)
{
    if(p=='*') p='o';
    else p='*';
    if(q=='*') q='o';
    else  q='*';
}

void dfs(int x,string s,int cnt)
{
    //cout<<s<<'\n';
    if(s==t) {
        //cout<<"hhh\n";
        //cout<<s<<'\n';
        ans=min(ans,cnt);
        return ;
    }
    if(cnt>ans||x>=len) return ;



    //翻转第x个位置以及第x-1 
    if(s[x-1]!=t[x-1]) {
        swap(s[x],s[x-1]);
        dfs(x+1,s,cnt+1);
    } 
    else {
        //不翻转
        dfs(x+1,s,cnt); 
    }
    //swap(s[x],s[x-1]);
}

int main()
{
    string s;
    cin>>s>>t;
    len=s.length();
    ans=0x3f3f3f3f;
    dfs(1,s,0);
    cout<<ans<<'\n';
    return 0;   
}

标题:寒假打卡——AcWing1208翻硬币
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/01/20/1611151981677.html