P9172题解

what_can_I_do · 2023-04-07 22:06:29 · 题解

传送门

模拟。先用一个数组 a 把 4 个字母分别存储下来，a_0 存 d，a_1 存 k，a_2 存 o，a_3 存 r。接着用深搜分别去枚举所有鳄鱼卡分别替代成的绿卡的所有情况。最后答案用一个函数求出，可以先把 a_0，a_1\div2，a_2\div2，a_3 的最小值求出来，作为 krokod 的数量，再乘 7，最后加上四中绿卡分别的数量的平方就行了。答案输出最大值。

CODE:

#include<bits/stdc++.h>
using namespace std;
int a[4],n,m,ans=-1;
inline int check()    //求每种情况的答案
{
    int sum=min(a[0],a[1]/2);
    sum=min(sum,a[2]/2);
    sum=min(sum,a[3]);
    sum*=7;
    for(register int i=0;i<4;i++) sum+=a[i]*a[i];
    return sum;
}
inline void dfs(int k)    //枚举所有情况
{
    if(k>m){ans=max(check(),ans);return;}
    for(register int i=0;i<4;i++) a[i]++,dfs(k+1),a[i]--;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++)    //统计数量
    {
        char ch;
        cin>>ch;
        if(ch=='d') a[0]++;
        if(ch=='k') a[1]++;
        if(ch=='o') a[2]++;
        if(ch=='r') a[3]++;
    }
    dfs(1);    //深搜
    printf("%d",ans);
    return 0;
}