寒假算法基础集训营5 F题题解

设使用了x个"qcjjkkt"和y个"td"则总长度约束为：7x+2y-min(x,y)≤n（减去 min(x, y) 是因为有 min(x, y) 个 "td" 可以节省一个字符）。最优解一定出现在几个关键点附近：

1.x=0（完全不使用 "qcjjkkt"）

2.x=n/7（最大可能的 "qcjjkkt" 数量）

3.x=n/8（平衡点）

4.在这些点附近 ±1 的位置（防止遗漏边界情况）

对以上点进行检查即可。

附本人ac码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 998244353
const ll N=1e6+10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        ll n,a,b;
        cin>>n>>a>>b;
        vector<ll>x;
    	x.push_back(0);// 完全不使用qcjjkkt
    	x.push_back(n / 7);// 最大可能数量
    	x.push_back(n / 8);// 平衡点
    	x.push_back(n / 8 - 1);// 平衡点左侧
    	x.push_back(n / 8 + 1);// 平衡点右侧
    	x.push_back(n / 7 - 1);// 最大值左侧
    	x.push_back(n / 7 + 1);// 最大值右侧
    	ll m=0;
		for (ll i:x) 
		{
        	if (i<0||7*i>n)continue;
        	ll rest=n-7*i;// 剩余可用长度
        	ll free=min(i,rest);// 能免费添加的'd'数量
        	ll normal= (rest-free)/2;// 正常构造的td数量
        	ll sum=free+normal;// 总td数量
        	ll score=a*i+b*sum; // 目标函数值
        	m= max(m, score);
    	}
    	cout<<m<<endl;
    }
    return 0;
}