自动搬运

查看原文

来自洛谷，原作者为

	篮网总冠军 Keep dreaming.Remain loving.

搬运于2025-08-24 23:17:41，当前版本为作者最后更新于2024-08-23 21:11:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解

废话不多说，开始讲题。

step -2 分析算法

首先我们分析一下这道题的算法。

很显然，这题要用 dp 做，但不能只用 dp，必须在前面进行一下排序，这题也就是一道典型的贪心 dp 题。

step -1：排除无用条件

通过读题，我们可以筛掉一些无用的条件。

因为时间越往后，每个比赛的等待时间会越来越长，所以你一定会把吃饭放到最后一个比赛结束后吃饭。

所以上来 $T\gets T-d$。

同时，你最后一定要留出回家的时间。

所以再 $T\gets T-x$。

step 0：分类讨论

我们可以看出，$c_i$ 是可能为 $0$ 的。如果 $c_i=0$，那么这场比赛无论何时参加时间都是 $a_i+b_i$，所以我们要把 $n$ 场比赛分成两部分，一部分是 $c_i=0$ 的，还有一部分是 $c_i \gt 0$的。我们先看 $c_i\gt0$ 的部分。

我们通过以下代码进行快排来分类：

bool cmp1(node x,node y){
    return x.c>y.c;
}

step 1.0：求出 $c_i$ 不为 $0$ 的比赛的个数

long long n1=0;
for(int i=1;a[i].c!=0;i++,n1++);

step 1.1：分析如何排序

我们通过读题，可以找到一些有用的条件。那么，我们现在来分析，对于第 $i$ 场比赛和第 $j$ 场比赛，是先去比第 $i$ 场再去比第 $j$ 场时间短，还是先去比第 $j$ 场再去比第 $i$ 场时间短？

我们可以列式。

在时刻 $t$，对于先去比第 $i$ 场再去比第 $j$ 场，总时间为 $x+c_i \times (x+t)+b_i+a_i+x+c_j \times (t+x+c_i \times (x+t)+b_i+a_i+x)+b_j+a_j$。

在时刻 $t$，对于先去比第 $j$ 场再去比第 $i$ 场，总时间为 $x+c_j \times (x+t)+b_j+a_j+x+c_i \times(t+x+c_j \times (x+t)+b_j+a_j+x)+b_i+a_i$。

因为要判断的是两个式子的大小，所以可以将相同的消掉。

化简得上面的式子为 $(x+a_i+b_i) \times c_j$。

下面的式子为 $(x+a_j+b_j) \times c_i$。

按照 $(x+a_i+b_i) \times c_j \lt (x+a_j+b_j) \times c_i$ 进行快排，排序完成。

bool cmp(node x1,node y){
    return (x+x1.a+x1.b)*y.c<(x+y.a+y.b)*x1.c;
}

为什么这样排序就对了呢？

考虑一个存在 $i,j$ 满足 $i<j$ 且 $(x+a_i+b_i) \times c_j \ge (x+a_j+b_j) \times c_i$ 的排列。显然除了刚才排序得到的排列，其他的任何排列都满足这一条件。

那么只要把第 $i$ 项和第 $j$ 项对调一下，答案一定不劣。最终可以始终不劣地调整为我们排序得到的排列。那么证毕。

step 1.2：预处理

除了上面的排除无用的条件的两步，还要对 dp 数组进行预处理。

自然应该先将所有数赋值 $10^9$，再将第一轮会用到的 $dp_{0,0}$ 赋值为 $0$。

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j]=1e9;
        }
    }
    dp[0][0]=0;

step 1.3：进行动态规划

在这里，$dp_{i,j}$ 代表在前 $i$ 场比赛中选择 $j$ 场比赛的最小时间。

对于第 $i$ 场比赛，我们应该干两件事。

首先，我们应该将所有这场比赛不选的情况放入 dp 中。

枚举前 $i$ 个选 $0 \sim i$ 个的情况。

for(int j=0;j<=i;j++){
            dp[i][j]=dp[i-1][j];
}

接着，我们应该将这场比赛选的情况更新。

枚举前 $i-1$ 个选 $0 \sim i-1$ 个的情况。

for(int j=1;j<=i;j++){
            if (dp[i-1][j-1]<T){
                long long t=x+a[i].a+(dp[i-1][j-1]+x)*a[i].c+a[i].b;
                if (t+dp[i-1][j-1]<=T) dp[i][j]=min(dp[i][j],t+dp[i-1][j-1]);
            }
        }

这里注意，如果时间超过 $T$ 就可以不求了。

step 1.4：优化

显然，$O(n^2)$ 肯定超过了时间复杂度。

那么，我们怎么才能进一步优化程序呢？

由于我们要 dp 的这一部分满足 $c_i \gt 0$，所以数据满足 $1 \le a_i,b_i,c_i \le 10^9$，那么我们来分析一下。

我们假设第一次打第 $r$ 场比赛，那么结束时时间为 $x+a_r+b_r+x \times c_r$。

再假设第二次打第 $p$ 场比赛，那么结束时时间为 $x+a_r+b_r+x \times c_r+x+c_p \times (x+a_r+b_r+x \times c_r+x)+a_p+b_p$。

再假设第三次打第 $u$ 场比赛，那么结束时间为 $x+a_r+b_r+x \times c_r+c_p \times (x+a_r+b_r+x \times c_r+x)+a_p+b_p+x+c_u\times(x+a_r+b_r+x \times c_r+c_p \times (x+a_r+b_r+x \times c_r+x)+a_p+b_p+x)+a_u+b_u$。

我们可以得出，对于第一次比赛，其结束时间不小于 $a_r+b_r$。

第二次比赛结束时间不小于 $(a_r+b_r) \times 2+a_p+b_p$。

第三次比赛结束时间不小于 $4 \times (a_r+b_r)+2 \times (a_p+b_p)+a_u+b_u$。

总结一下，我们可以得出，第 $i$ 次比赛结束时间一定不小于 $2^i$，所以最多只能参加 $\log(T)$ 场比赛。

所以我们就可以简化复杂度到 $O(n \times \log(T))$。

此复杂度的 dp 代码如下：

for(int i=1;i<=n1;i++){
        for(int j=0;j<=min(31,i);j++){
            dp[i][j]=dp[i-1][j];
        }
        for(int j=1;j<=min(31,i);j++){
            if (dp[i-1][j-1]<T){
                long long t=x+a[i].a+(dp[i-1][j-1]+x)*a[i].c+a[i].b;
                if (t+dp[i-1][j-1]<=T) dp[i][j]=min(dp[i][j],t+dp[i-1][j-1]);
            }
        }
    }

这里注意， $31$ 是因为 $\log(T)$ 不会超过 $31$。

step 2.1：贪心

我们想想，当一个区间 $c_i=0$ 时，应该怎么排序呢？

当然是把 $a_i+b_i$ 从小到大排序。

bool cmp2(node x,node y){
    return x.a+x.b<y.a+y.b;
}

step 2.2：求前缀和

为了方便之后查找剩余时间够打几场比赛，我们应该先求出排完序后的后半部分的前缀和。

for(int i=n1+1;i<=n;i++){
        s[i]=s[i-1]+a[i].a+a[i].b+x;
    }

step 2.3：更新答案

枚举在 $c_i \gt 0$ 这一部分中选 $0 \sim \min(n_1,\log(t_1))$ 个的可能，再在刚刚准备好的前缀和表中二分查找最多能选的个数，并不断更新最大值，最后输出即可。

long long sum=0;
for(int i=min(31ll,n1);i>=0;i--){
        long long o=dp[n1][i];
        if (o>T) continue;
        long long r1=T-o;
        int l=n1,r=n;
        while(l<r){
            int mid=(l+r+1)/2;
            if (s[mid]<=r1) l=mid;
            else r=mid-1;
        }
        sum=max(sum,l-n1+i);
    }
    cout<<sum<<endl;