题解 | F

题目

输入

输出

思路

设dp[i]为前i项最大的快乐值，根据题目可以发现dp[i]=max(dp[i],dp[i-1],dp[i-2]+b,dp[i-7]+a,dp[i-8]+a+b);

观察数据大小发现，n特别大时，直接暴力会超时。可以找2，7，8的最小公倍数，将n以56为一组进行贪心。

为了最大化利用n/56的余数，所以组数要减一。

完整代码

```#include<bits/stdc++.h>
using namespace std;
int main(){
    int  t;
    cin>>t;
    while(t--){
        int n;
        long long a,b;
        cin>>n>>a>>b;
        vector<long long> dp(125); dp[0]=0;
        if(n<125){
        for(long long i=1;i<125;i++){
            dp[i]=dp[i-1];  
            if(i>=7) dp[i]=max(dp[i],dp[i-7]+a);
            if(i>=2) dp[i]=max(dp[i],dp[i-2]+b);
            if(i>=8) dp[i]=max(dp[i],dp[i-8]+a+b);
        }
        cout<<dp[n]<<'\n';
        continue;
        }
        else{
        long long ans=0;
        long long shu1=28*b;
        long long shu2=a*8;
        long long shu3=7*(a+b);
        long long da=0;
            if(shu1>da) da=shu1;
            if(shu2>da) da=shu2;
            if(shu3>da) da=shu3;
        long long cnt=n/56;
        ans=(cnt-1) * da;     
        long long res=n-(56*(cnt-1));
        for(int i=1;i<=res;i++){
            dp[i]=dp[i-1];
            if(i>=2) dp[i]=max(dp[i],dp[i-2]+b);
            if(i>=7) dp[i]=max(dp[i],dp[i-7]+a);
            if(i>=8) dp[i]=max(dp[i],dp[i-8]+a+b);
        }
           
        ans+=dp[res];
          cout<<ans<<'\n';
        }
    }
    return 0;
}