题解

· · 题解

题解

废话不多说，开始讲题。

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;