题解：AT_kupc2016_i 一坨日文看不懂思密达

2huk · 2024-11-22 15:35:08 · 题解

考虑只有一次询问怎么做。

考虑 DP。设 f(i, j) 表示若最开始有一个等级为 i 的机器人，在 j 秒内最多能发多少张传单。转移有：

表示接下来这个机器人是否复制至少一个。当然后者能转移的前提是 j \ge ic。答案为 f(1,n)。

不难发现一个机器人最终的等级不会很大。升到某个级别的所花事件是一个等差数列，也就是说它的等级最大 \sqrt n。所以第一维是 \mathcal O(\sqrt n) 的。所以一次询问的复杂度是 \mathcal O(n \sqrt n)。

对吗？

注意到 f 的值会很大（所以题目要求取模），这个 \max 不好做。写高精度复杂度肯定不对。因此考虑挖掘一些性质，避开这个比较，直接转移。

注意到，让等级为 i 的机器人再复制一个后，答案至少为 2(j-ci)，即这两个不会再复制，而是一直发传单到结束。

那么如果 2(j-ci) \ge j，即复制一个一定不劣于不复制，那么一定选择复制。换言之 f(i,j) 会从 f(i,j-ci)+f(i+1,j-ci) 转移过来。

否则如果 j > 2(j-ci)，是否不复制一定最优呢？

是的。因为这等价于 j < 2ci，其意义是剩下的 j 时间内无法复制 \ge 2 个机器人，也就是最多复制 1 个。而复制 1 个不优，所以就不复制了。换言之 f(i,j) 会从 f(i,j-ci)+f(i+1,j-ci) 转移过来。

这样就解决了一次询问。

考虑多次询问。

注意到最终能直接或间接转移到 f(i,j) 的所有状态 f(i',j') 一定满足 j \equiv j' \pmod c。这里有点类似完全背包。

所以重新令 f'(i,j)=f(i,jc)。不难发现：

所以答案就是 f'(1,\lfloor n/c \rfloor) \times c。乘 c 的原因是第二种转移时状态值不对。

显然不对。因为还剩 n \bmod c 的时间我们没有考虑。显然在这点时间里没有机器人能来的及再复制。因此我们记录 g(i,j) 表示考虑一个等级为 i 的机器人在 j 个时间内传单数量最多的情况下，最多复制几个机器人（包括自己）。

然后答案为 f'(1,\lfloor n/c \rfloor) \times c + g(1,\lfloor n/c \rfloor) \times (n \bmod c)。

// Problem: 
//     ティッシュ配り
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_kupc2016_i
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// #define tests
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, P = 1e9 + 7;

int q, n, c;
int f[500][N], g[500][N];

void solve() {
    for (int i = 498; i; -- i )
        for (int j = 1; j < N; ++ j ) {
            if (j >= i * 2) {
                // 生更好
                f[i][j] = (f[i + 1][j - i] + f[i][j - i]) % P;
                g[i][j] = (g[i + 1][j - i] + g[i][j - i]) % P;
            } else {
                f[i][j] = j;
                g[i][j] = 1;
            }
        }

    cin >> q;
    while (q -- ) {
        cin >> n >> c;
        cout << (1ll * f[1][n / c] * c + 1ll * g[1][n / c] * (n % c)) % P << '\n';
    }
}

signed main() {
    freopen("robot.in", "r", stdin);
    freopen("robot.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
#ifdef tests
    cin >> T;
#endif
    while (T -- ) solve();
    return 0;
}