题目描述:

alt

输入描述:

alt

输出描述:

alt

思路:

采用动态规划(dp)

分为3类:td qcjjkkt qcjjkktd 大小为2,7,8最小公倍数为56

当n极大 把大部分按照最有重复剩下用dp，当n极大分为3种全td 全qcjjkkt 全qcjjkktd取最大值

剩下部分 i-2基础上加上td i-7基础加上qcjjkkt i-8基础加上qcjjkktd

using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--){
        long long n,a,b;
        cin>>n>>a>>b;
        long long sum=0;
        if(n>56){//重复块最优化
            long long m=max({b*28,a*8,(a+b)*7});
            long long cnt=n/56;
            sum+=(cnt-1)*m;
            n-=56*(cnt-1);
        }
        vector<long long>ans(n+1);
        for(int i=1;i<=n;i++){
            if(i>=2) ans[i]=max(ans[i],ans[i-2]+b);//加上td
            if(i>=7) ans[i]=max(ans[i],ans[i-7]+a);//加上qcjjkkt
            if(i>=8) ans[i]=max(ans[i],ans[i-8]+a+b);//加上qcjjkktd
        }
        sum+=ans[n];
        cout<<sum<<"\n";
    }
}