题目：传送门

题意：有 n 个店，一开始你在家，此时 t = 0，你可以花 1 单位时间从你家去任意的一个店，或者从某一个店去到另一个店。假设你在 t = x 的时候到达第 i 个店，那么你需要花 ai*x + bi 的时间在这个店买东西。现在问你在 T 单位时间内最多能去几个店买东西。

1 <= n <= 2e5,  0 <= ai <= 1e9, 0 <= bi <= 1e9, 0 <= T <= 1e9

 

思路：

假设现在你有两个店 i, j，此时 t = x，若选择 i 比选择 j 更优，则需要满足：

1 + ai * (x + 1) + bi + 1 + aj * (x + 1 + ai * (x + 1) + bi + 1) + bj   <   1 + aj * (x + 1) + bj + 1 + ai * (x + 1 + aj * (x + 1) + bj + 1) + bi

化简一下，得到  aj * (bi + 1)  <  ai * (bj + 1)

那么我们就可以按照上面的规则，排序。 然后 DP

dp[ i ][ j ] 前 i 个店在 j 家店买东西需要花的最少的时间。

然后第一维可以直接优化掉，直接当成 01 背包做 dp。

但是这样的 DP 是 o(n^2) 的，需要考虑优化。

可以根据 ai 的值进行分类，我们发现若 ai != 0，那么每次的时间都至少是成倍增加的，也就是说每在一个店买东西，时间就会 * 2，而 T <= 1e9，那么就是说对于 ai != 0 的店最多只能去 log(T) 个店买东西。

那么我们直接对 ai != 0 的做一遍 dp，第二层 for 最多只有 log(T) 个，那么复杂度就很可观了。然后对每个 dp ，找一下剩下的时间能去多少个 ai == 0 的店即可。

 

#include <bits/stdc++.h>
#define LL long long
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF INT_MAX
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
using namespace std;

const int N = 2e5 + 10;

pair < LL, LL > a[N], tmp;
LL c[N];
LL dp[100];

bool cmp(pair < LL, LL > A, pair < LL, LL > B) {
    return A.fir * (B.sec + 1) > B.fir * (A.sec + 1);
}

void solve() {

    int n; LL T;
    scanf("%d %lld", &n, &T);
    int cnt1 = 0, cnt2 = 0;
    rep(i, 1, n) {
        scanf("%lld %lld", &tmp.fir, &tmp.sec);
        if(tmp.fir == 0) c[cnt2++] = tmp.sec + 1;
        else a[cnt1++] = tmp;
    }

    sort(c, c + cnt2);
    sort(a, a + cnt1, cmp);

    rep(i, 1, 30) dp[i] = T + 1;
    dp[0] = 0;
    rep(i, 1, cnt2 - 1) c[i] += c[i - 1];

    rep(i, 0, cnt1 - 1) {
        dep(j, 1, 30) {
            dp[j] = min(dp[j], (a[i].fir + 1) * (dp[j - 1] + 1) + a[i].sec);
        }
    }

    int ans = 0;
    rep(i, 0, 30) {
        if(dp[i] > T) continue;
        int add = 0;
        if(cnt2) add = upper_bound(c, c + cnt2, T - dp[i]) - c;
        ans = max(ans, i + add);
    }
    printf("%d\n", ans);
    return ;
}

int main() {

    solve();

    return 0;
}