昨天没解决的题目

昨天我遭遇一道算法题。我面对它完全没有头绪，以为自己能轻易地解决它，于是在比赛中使用“一半的比赛时间”（2小时）尝试解决它，不仅消耗了宝贵的寒假时间，而且最后未能通过，从而遗 憾 离 场。

问题：F-智乃的算法竞赛群友_2026牛客寒假算法基础集训营5

题目描述

智乃加了一个算法竞赛群，她发现里面的群友各个都是人才，说话又好听。 她发现每次管理员qcjj在发比赛链接时，群友都会往下复读什么qcjjkkt（清楚姐姐看看题）和td（题单）。 现在你想要在群里发言，具体来讲，你希望使用几个字符组成一句话。 这句话可以视为是一个长度为 的字符串，其每包含一个 qcjjkkt 子串，你获得 的快乐值，每包含一个td子串，获得 的快乐值。问能够在群中通过这次发言得到的最大快乐值是多少。 注意子串可以包含公共部分，例如qcjjkktd可以同时包含qcjjkkt和td。

我一开始想到完全背包，背包的容量为 ，可以放入的物品为 qcjjkkt、td和qcjjkktd，它们的代价分别为7、2和8，而价值为 、和。没有其他的子串变体。只是 高达 ，需要进行某种优化。

起始时，我注意到了7、2和8的最小公倍数是56。于是对容量为56的情况做了一次完全背包dp，之后对于给定的，先检查它有多少个56,用的结果乘以它，接着剩余部分取出dp中相应的值。

但打表发现这是错的。经过大量时间无法修正。

目前发现有两种方法。

法1

阅读官方题解，有一个和这种做法类似的描述，其中提到：

作者：四糸智乃
链接：https://ac.nowcoder.com/discuss/1609734
来源：牛客网

首先注意到只有三种决策

1. 填充td
2. 填充qcjjkkt
3. 填充qcjjkktd

三种决策的长度分别为2，7，8，最小公倍数是56，如果n=k*56，那么问题变得非常简单，直接贪心使用一种决策填满

否则剩余的部分一定小于56，对于这个数据范围，爱怎么搞怎么搞，无论是dp还是枚举都能够很方便的通过本题

(PS：对于这类问题，可以使用AC自动机(max,+)转移矩阵快速幂求解，感兴趣可自行了解)

于是我又写了下面的代码尝试测评，结果又无法通过了。

#include <algorithm>
#include <iostream>
using namespace std;
using ll=long long;

void solve(){
    ll n,a,b;
    cin>>n>>a>>b;
    ll c[4]={0,a,b,a+b};
    ll w[4]={0,7,2,8};
    ll dp[4][58]={0};
    for(int i=1;i<=3;i++){
        for(int j=1;j<=56;j++){
            if(j<w[i])
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]);
        }
    }
    ll base=n/56,ans=0;
    if(base){
        ans=base*max(max(a*8,b*28),(a+b)*7);
    }
    ans+=dp[3][n%56];
    cout<<ans<<'\n';
}
    
int main(){
    int t;
    cin>>t;
    while(t--)solve();
}

与AI交流讨论后发现无论是最初的做法，还是采用官方题解的做法，都存在一个要考虑的事情：从56段中"借"一点空间给余数段，可能整体更优。但是最多可能需要借多少份物品？测试发现最多借到dp的允许计算范围 就行了，原因尚未了解。

//#include <corecrt_math.h>
#include <algorithm>
#include <iostream>
using namespace std;
using ll=long long;

/*
1   
68 54 9
------
531
522
*/

//智乃的算法竞赛群友
//zhinaisolve
void solve(){
    ll n,a,b;
    cin>>n>>a>>b;
    ll c[4]={0,a,b,a+b};
    ll w[4]={0,7,2,8};
    ll dp[4][57]={0};
    for(int i=1;i<=3;i++){
        for(int j=1;j<=56;j++){
            if(j<w[i])
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]);
        }
    }
    ll ans=0;
    for(int i=1;i<=3;i++){
        if(n<w[i])continue; //无法选择
        ll k=n/w[i]; //最多选k个物品i
        ll rem = n%w[i]; //余数;
        for(int dt=0; rem+1LL*dt*w[i]<=56&&dt<=k;dt++){
            ll r=rem+1LL*dt*w[i];
            ll val = (k-dt)*c[i]+dp[3][r];
            ans=max(ans,val);
        }
    }
    cout<<ans<<'\n';
}

int main(){
    int t;
    cin>>t;
    while(t--)solve();
}

法2

直接枚举 （qcjjkkt 数量）在关键点附近的值。这需要使用数学方法求解关键点。

不过仍然可以认为这是完全背包问题。有三件物品， qcjjkkt、td和qcjjkktd。它们的状况如下。

物品	代价()	快乐值（）
qcjjkkt	7
td	2
qcjjkktd	8
容量：

设在最终的字符串中能够选取 个后不接 d 的 qcjjkkt，选取 个前不接 qcjjkk 的td，以及 个 qcjjkktd，它们满足约束条件：代价 .

其快乐值 . 记 （子串qcjjkkt计数），（子串td计数），则，，快乐 .

则此时代价 ，其中.

为最小化代价，取 . 这总可以且应该做到，因为对于决定选取的所有qcjjkkt和td，总可以将它们组成 个 qcjjkktd，这不仅能保留它们的价值，还能减少长度。

对于给定的，

①若 ， 则代价 . 的最大值 （这要求 ），此时最大快乐值

其中 为取整造成的偏移.注意到 ，则仅与 有关，这在一次计算中是相同的，可看做常数，且 .（不过这个范围没有用处，重要的是这是常数，这意味着的线性性不会被破坏。）

而 ，则，则当 时，.

②否则若，则代价 . 取 （不用取整，这要求 ），此时最大快乐值

而 ，则 ，又 ，则当 时， .

那么当 时，

1. 若， 越大越好，则最大快乐值在 附近 取得。
2. 若，则所有 等价。
3. 若， 越小越好，则最大快乐值在 取得。

当 时，

1. 若 ： 越大越好， 附近 取得。
2. 若 ： 越小越好，。
3. 若 ：等价。

不在这个范围内意味着无解。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll=long long;

void solve(){
    ll n,a,b;
    cin >>n>>a>>b;
    ll ans=0;
    ll can[]={0,n/8-1,n/8,n/8+1,n/7-1,n/7,n/7+1};
    for(ll x:can){
        if(x<0) continue;
        if(n>=8*x){
            ll y=(n-6*x)/2;
            if(y<0)continue;
            ans=max(ans,x*a+y*b);
        }else if(7*x<=n && n<8*x){
            ll y=n-7*x;
            if(y<0) continue;
            ans=max(ans,x*a+y*b);
        }
    }
    cout<<ans<<'\n';
}

int main(){
    int t;
    cin>>t;
    while(t--)solve();
}