警示后人:如果你 TLE on #2
查看原帖
警示后人:如果你 TLE on #2
338632
robinyqc楼主2024/12/20 11:29

如果你是双 log 值域的做法,请不要进行 nlog2Vn\log^2 V 次除法,否则会 TLE on #2。把背包改成递推(因为这里可以递推)。

也就是把这种:

dp[x].fill(INF);
for (u32 i = 63; ~i; i--) {
    for (u32 j = 0; i + j < 64; j++) {
        to_min(dp[x][i + j], nw[i]);
        nw[i] = (nw[i] + b[x] - 1) / b[x];
    }
}

换成这种:

for (u32 i = 1; i < 64; i++) {
    to_min(nw[i], (nw[i - 1] + b[x] - 1) / b[x]);
}
dp[x] = nw;

赛时就差这个。我的 master 啊 QAQ.

2024/12/20 11:29
加载中...