题解 | #智乃的算法竞赛群友#

F题

这题比较容易写的算法可以是动态规划（全用分类讨论写wa了好多发T_T），但是直接暴力的话会超时，这时候大概分三大情况，要么qcjjkkt，要么td，要么qcjjkktd，如果分类讨论继续往下写的话，由于qcjjkktd可以同时包含另外两个，讨论时就会出现很多种情况，细分下去容易出错，但是用动态规划就不用考虑那么多，细想之下就会发现当字符串长度为56时，三种情况刚好凑满，只需要先算出长度为56的字符串所能得的最大分，然后只要对最后模56剩下来的长度进行小范围动态规划就行（注意由于字符串可包含，要再将上一个56长度的字符串加上一起进行计算）

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;cin>>t;
    while(t--){
        long long n,a,b;cin>>n>>a>>b;
        long long sum=max(max(b*28,a*8),7*(a+b));
        long long F[113]={0};
        long long size=n/56-1;
        long long left=n%56+56;
        if(size==-1){
            for(long long i=1;i<=left-56;i++){
                if((i-1)>=0) F[i]=max(F[i],F[i-1]);
                if((i-2)>=0) F[i]=max(F[i],F[i-2]+b);
                if((i-7)>=0) F[i]=max(F[i],F[i-7]+a);
                if((i-8)>=0) F[i]=max(F[i],F[i-8]+a+b);
            }
            cout<<F[left-56]<<endl;
        }
        else{
            for(long long i=1;i<=left;i++){
                if((i-1)>=0) F[i]=max(F[i],F[i-1]);
                if((i-2)>=0) F[i]=max(F[i],F[i-2]+b);
                if((i-7)>=0) F[i]=max(F[i],F[i-7]+a);
                if((i-8)>=0) F[i]=max(F[i],F[i-8]+a+b);
            }
            cout<<F[left]+sum*size<<endl;
        }
    }
}