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

题解

一共三种情况1.td 2.qcjjkkt 3.qcjjkktd。分别长度为2，7，8。最小公倍数是56。

如果是56的倍数的话，就用贪心，看哪种组合最大就行。

不足56就用dp，但注意的如果留的不足56又会有可能错过最优解，所以得至少留56， 即n%56+56。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        long long n,a,b;
        cin>>n>>a>>b;
        long long sum=0;
        if(n>56){
            long long ans=max({b*28,a*8,(a+b)*7});
            long long m=n/56;
            sum=(m-1)*ans;
            n=n-(m-1)*56;
        }
        vector<long long> arr(n+1);
        for(int j=1;j<=n;j++){
            if(j>=2) arr[j]=max(arr[j],arr[j-2]+b);
            if(j>=7) arr[j]=max({arr[j],arr[j-7]+a});
            if(j>=8) arr[j]=max(arr[j],arr[j-8]+a+b);
        }
        sum+=arr[n];
        cout<<sum<<endl;
    }
}