D题题意：

有 n种果子，第 i 种有ci 个，每个重量 wi。一开始每个果子单独成一堆，总堆数 = ∑c i​ 。每次可以选两堆合并，代价 = 新堆重量，代价会累加。要求把所有果子合并成一堆的最小总代价，答案对 10 9+7取模。

核心思路：

把每个果子都看成一个叶子节点，权重就是它的重量 w i​。 每次合并当前重量最小的两堆，用 小根堆（优先队列）维护。 总代价就是所有非叶子节点的权值和。

#include<bits/stdc++.h>
 
using namespace std;
 
using LL = long long;
 
const LL M = 1e9 + 7;
 
int main(){
    int n;
    cin >> n;
    map<LL, LL> mp;//这里使用map代替了堆得功能，因为map会自动按key升序排序。
    LL cnt = 0, ans = 0;
    for(int i = 1; i <= n; i++){
        int c, w;
        cin >> c >> w;//数量，重量
        mp[w] += c;//对应重量的数量+=c
        cnt += c;//总数
    }
    while(cnt > 1){//如果总数不小于等于1
        auto [x, y] = *mp.begin();//map.begin()是最小key,结构化绑定取key和value。
        mp.erase(mp.begin());//从map中移除这个最小重量。
        if(y > 1){
            mp[x * 2] += y / 2;//每两个合并成一个2x,数量是y/2
            //累加这部分合并的代价，每个合并贡献代价2x,共y/2个
            ans = (ans + (x * 2 % M) * (y / 2 % M)) % M;
            cnt -= y / 2;//总数量减少
            if(y % 2 == 0) continue;//如果y是偶数
        }
        //y不是偶数，合并后还有剩下的
        auto &[x1, y1] = *mp.begin();//取当下最小的重量，及其数量【引用，修改x1等效修改key】
        mp[x1 + x] += 1;//合并代价
        ans = (ans + x1 + x) % M;//累加代价
        cnt--;
        y1--;//该数量-1
        if(!y1) mp.erase(mp.begin());//判断一下有没有减到0，如果减到了就移除
    }
    cout << ans << endl;
}

F题题目：

现在你想要在群里发言，具体来讲，你希望使用 n个字符组成一句话。 这句话可以视为是一个长度为 n 的字符串，其每包含一个 qcjjkkt子串，你获得 a的快乐值，每包含一个 td 子串，获得b 的快乐值。问能够在群中通过这次发言得到的最大快乐值是多少。

核心思路：

  1. 先明确「最优单段收益」（贪心基础） 首先计算每 56 个单位（2、7、8 的最小公倍数） 能获得的最大单段收益 per： b28：56 个单位全用 2 单位操作（56/2=28 次）的收益； a8：56 个单位全用 7 单位操作（56/7=8 次）的收益； (a+b)*7：56 个单位全用 8 单位组合操作（56/8=7 次）的收益； per 取这三者的最大值，代表每 56 个单位能拿到的最优固定收益。
  2. 大数值分段贪心（减少 DP 计算量） 当 n > 112 时（112=562），先拆分出「整数个 56 段」做贪心： 计算能拆出的 56 段数量 f = n/56 - 1（留一段 56 以内的数用 DP 计算，避免边界问题）； 总收益先累加 f * per（每段 56 拿最优收益）； 剩余 n = n - f56（剩余数量≤112，用 DP 精确计算）。
  3. 小数值动态规划（精确求解） 对剩余的小数值 n（≤112），用 DP 计算最大收益： 状态定义：dp[i] 表示「用了 i 个单位」能获得的最大收益； 状态转移（枚举所有可能的操作）： 选 2 单位操作：dp[i] = max(dp[i], dp[i-2] + b)（i≥2）； 选 7 单位操作：dp[i] = max(dp[i], dp[i-7] + a)（i≥7）； 选 8 单位组合操作：dp[i] = max(dp[i], dp[i-8] + a+b)（i≥8）； 初始状态：dp[0] = 0（0 个单位收益为 0）。
  4. 最终结果 总收益 = 贪心段收益 + DP 段收益，输出结果。
#include <bits/stdc++.h>
using namespace std;
void sol()
{
    long long n,a,b;
    cin>>n>>a>>b;
    long long per=max({b*28,a*8,(a+b)*7});
    long long ans=0;
    if(n>112)
    {
        long long f=n/56-1;
        ans+=f*per;
        n-=f*56;
    }
    vector<long long> dp(n+1,0);
    for(int i=1;i<=n;i++)
    {
        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[n];
    cout<<ans<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        sol();
    return 0;
}