寒假训练营5 题解

F-智乃的算法竞赛群友(完全背包问题)

贪心+dp/枚举

长度2，7，8的最小公倍数为56，以56为单位长度计算"td"、"qcjjkkt"、"qcjjkktd"三种策略的快乐值，找出最大的一种

将总长度n分为>800与<=800两部分，前者直接选取最大的策略填充，后者采用dp找出最优的填充方式

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
void solve()
{
    int T;
    cin>>T;
    while(T--){
        int n,a,b;
        cin>>n>>a>>b;
        vvi t={
            {56*a/7,7,a},
            {56*b/2,2,b},
            {56*(a+b)/8,8,a+b}
        };//计算56(lcm)的收益进行比较
        sort(t.begin(),t.end());//按单位长度收益排序
        int c=t[2][1],v=t[2][2];//选取单位长度收益最高的策略，c为该策略的长度，v为该策略的收益
        int cnt=max(0ll,n/c-100);//贪心：最优策略做尽可能多次，但留100次给DP处理边界情况
        //max两个参数类型必须相同，要用0ll
        int ans=cnt*v;//贪心部分的收益
        n-=cnt*c;//dp部分长度(<=800)
        vector<int>f(n+1);
        for(int i=1;i<=n;i++){//遍历每个长度
            if(i>=2) f[i]=max(f[i],f[i-2]+b);
            if(i>=7) f[i]=max(f[i],f[i-7]+a);
            if(i>=8) f[i]=max(f[i],f[i-8]+a+b);
        }
        cout<<ans+f[n]<<"\n";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}