如果你是双 log 值域的做法,请不要进行 nlog2V 次除法,否则会 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.
