dfs

0
14

题目描述:

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

<

发布回复

请输入评论!
请输入你的名字