题目描述

智乃加了一个算法竞赛群，她发现里面的群友个个都是人才，说话又好听。 她发现每次管理员 qcjj 在发比赛链接时，群友都会往下复读什么 qcjjkkt（清楚姐姐看看题）和 td（题单）。 现在你想要在群里发言，具体来讲，你希望使用 n 个字符组成一句话。 这句话可以视为是一个长度为 n 的字符串，其每包含一个 qcjjkkt 子串，你获得 a 的快乐值，每包含一个 td 子串，获得 b 的快乐值。问能够在群中通过这次发言得到的最大快乐值是多少。 注意子串可以包含公共部分，例如 qcjjkktd 可以同时包含 qcjjkkt 和 td。

思路：

最终答案无疑是x个a和y个b，我们只需要考虑三种情况，1是全为td时，2是全为qcjjkkt(7)时，3是两者皆有，前面两者情况无需多言，全为qcjjkkt(7)中把%7后剩下的值尽数变为td就好，主要看第三种情况,第三种情况又可以分为两种，其一是全为qcjjkktd，%8后的余数变为td，即x个qcjjkktd加上y个单独的td，其二是x个qcjjkktd(8)和y个qcjjkkt(7)，第一中情况很好理解，第二种情况中，n%8必有余数，且用qcjjkktd(8)的对数加上n%8的余数大于等于7（不满足该条件的情况已被包含在n可以被8整除以及x对qcjjkkt(7)和y对td中），否则n/8即为第三种情况的最优解，满足条件后我们判断需要拆多少个qcjjkktd（每个拆一个d），才能把n%8补成7，我们用需要拆的qcjjkkt(7)对数加上凑出来的一对乘a，再加上没被拆的qcjjkktd(8)对数乘（a+b),该情况可以把每个空间都利用到，最后对比几种情况取最大值即可。

可能有人跟我有一样的疑惑，全为td的情况下，如果n%2==1的时候，我下三对td，上一对qcjjkkt（7）会不会变得更大，先说结论，不会，因为这是全td，这意味着qcjjkkt可以和一个td共用t，那么可以视为qcjjkkt（7）只要6个空间，此时明显用td更划算。

代码如下：

void solve() 
{
	ll len,sum=0,a,b,mn;
    cin>>len>>a>>b;
    sum=len/7*a;
    mn=min(len/7,len%7);
    if(mn==len/7)
        sum+=mn*b+(len%7-mn)/2*b;
    else sum+=mn*b;
    sum=max(sum,len/2*b);
    sum=max(sum,len/8*(a+b)+len%8/2*b);
    ll left=len%8,cnt=len/8;
    if(left+cnt>=7)
    {
        ll num=7-left;
        cnt-=num;
        sum=max(sum,(num+1)*a+cnt*(a+b));
    }
    cout<<sum<<endl;
}

如有错误，烦请指正谢谢