没开O2
by _Iva @ 2022-09-30 21:56:33
~~洛谷机子还是太快了~~
by AkeuchiTsuzuri @ 2022-09-30 21:57:26
正确的。
我看这道题的时候就感觉能通过类似单调队列优化多重背包的方法做到 $O(n4S)$ 的复杂度。
by T_E_I_O_ @ 2022-11-11 17:42:48
乐，时间跟别人差了几倍
https://www.luogu.com.cn/record/93603540
by T_E_I_O_ @ 2022-11-11 19:43:21
跑n次多重背包，(类似单调队列优化，但这里不需要单调队列，记录一下可以转移过来的和即可)，可以AC但是还是慢了很多
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define C 4
#define S 100005
int c[C], d[C];
typedef long long ll;
ll dp[C][S];
int main() {
int i, j, k, n, s;
ll num;
for (i = 0; i < C; i++) scanf("%d", &c[i]);
scanf("%d", &n);
while (n--) {
for (i = 0; i < C; i++) scanf("%d", &d[i]);
scanf("%d", &s);
memset(dp, 0, sizeof(dp));
for (i = 0; i <= d[0] && i * c[0] <= s; i++) dp[0][i * c[0]] = 1;
for (i = 1; i < C; i++)
for (j = 0; j < c[i]; j++) {
num = 0ll;
for (k = 0; k <= (s - j) / c[i]; k++) {
num += dp[i - 1][j + k * c[i]];
if (k > d[i]) num -= dp[i - 1][j + (k - d[i] - 1) * c[i]];
dp[i][j + k * c[i]] = num;
}
}
printf("%lld\n", dp[C - 1][s]);
}
exit(0);
}
```
by rediserver @ 2023-03-12 21:06:05
如果这个题改成n=1然后把硬币种数增大，直接多重背包还是不错的
by rediserver @ 2023-03-12 21:09:19