dfs

题目描述：

 

 

 

 AC代码：

#include<iostream>
#define int long long
using namespace std;
const int N = 30;
int vis[N][30],n,temp[N];
int ans = 0;
string s;

void dfs(int id,int t,int a[])
{
    //判断是否有越界 
    if(id >= n)
    {
        //对26个字母处理 
        for(int i = 0;i < 26;i++)
            if(a[i] != 0)
                return ;
        ans = max(ans,t);
        return ;
    }
    int newa[N];
    for(int i = 0;i < 26;i++)
        newa[i] = (a[i] + vis[id][i]) % 3;
    dfs(id + 1,t + 1,newa);
    dfs(id + 1,t,a);
}

signed main()
{
    cin >> n;
    for(int j = 1;j <= n;j++)
    {//j=1表示第一个字符串，比如为AABBCCC，则经过下一个for循环后的结果代表的含义如下：
    //vis[1][0] = 2 为A的个数
    //vis[1][1] = 2 为B的个数
    //vis[1][2] = 0 其实是3个的，但是3个已经满足条件了，就mod3当作0个来处理
    //其他的字符串也是如此操作
    //最后将所有字符串都存入二维数组vis当中，再对二维数组vis进行深搜 
        cin >> s;
        //一个for循环将所有的字符串转化为各个字母的出现次数，用一个二维数组记录 
        for(int i = 0;i    < s.size();i++)
        {//大写的A的ASCII码为65，s[i] - 'A'实际上少了1，故在右侧的赋值语句中需要+1后再根据题意mod3 
            
            vis[j][s[i] - 'A'] = (vis[j][s[i] - 'A'] + 1) % 3;
        }
    }
    //从第一个字符串开始，id初始为1 
    dfs(1,0,temp);
    cout << ans << endl;
    return 0;
}//vis[1][0] = (vis[1][0] + 1) % 3

原文链接:https://www.cnblogs.com/biaobiao88/p/12105217.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有