题目意思

智乃加入了一个算法竞赛群，她想要在群里用 n个字符组成一句话。这句话中每包含一个子串 "qcjjkkt"可以获得 a点快乐值，每包含一个子串 "td"可以获得 b点快乐值。子串可以重叠（例如 "qcjjkktd"同时包含 "qcjjkkt"和 "td"）。目标是最大化快乐值。

核心思路

本题采用贪心,关键观察是只有三种有效的子串模式：

"td"：长度 2，快乐值 b

"qcjjkkt"：长度 7，快乐值 a

"qcjjkktd"：长度 8，快乐值 a + b

这三种模式长度的最小公倍数是 56。对于较大的 n（n > 112），先贪心处理 56 的倍数部分：计算每种模式在 56 长度内能提供的快乐值（a8、b28、(a+b)*7），取最大值填充大部分长度。剩余部分（n % 56）通过动态规划预处理 0~112 长度内的最大快乐值（无限背包问题）。对于小 n（n ≤ 112），直接输出动态规划结果。

输入描述

第一行输入整数 T（1 ≤ T ≤ 10⁵）表示测试数据组数。每组数据包含三个正整数 n, a, b（1 ≤ n, a, b ≤ 10⁹），分别表示字符串长度、子串对应的快乐值。

输出描述

对于每组测试数据，输出一个整数，表示能获得的最大快乐值。

代码

#include<bits/stdc++.h>
#include <functional>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
#define endl '\n'

int main() {
    IOS;
    int T;
    cin >> T;
    while (T--) {
        ll n, a, b;
        cin >> n >> a >> b;
        ll c = a + b;
        ll w[3] = {7, 2, 8}; // 三种子串长度
        ll v[3] = {a, b, c}; // 对应快乐值
        ll dp[113] = {0};    // 动态规划数组，覆盖 0~112 长度

        // 无限背包预处理小范围最大快乐值
        for (int i = 0; i < 3; i++) {
            for (int j = w[i]; j <= 112; j++) {
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }

        if (n <= 112) 
            cout << dp[n] << endl;
        else {
            ll f1 = a * 8;  
            ll f2 = b * 28;  
            ll f3 = c * 7;  
            ll mp = max({f1, f2, f3});
            // 贪心处理大部分长度，剩余部分用 dp 计算
            ll ans = mp * (n / 56 - 1);
            ans += dp[n % 56 + 56];
            cout << ans << endl;
        }
    }
    return 0;
}

示例

输入：

3
10 9 1
1000000000 1000000000 1000000000
1 1 4

输出：

11
500000000000000000
0