题目分析：这题的数据量实在感人，三层循环(枚举种类，枚举数值，枚举个数)肯定超时，要想办法减去一层循环，仔细分析可以发现个数的那层循环可以省掉，代价是耗费更多的空间，，开一个cnt数组记录当前第i种使用了多少个，其它两层循环不变，然后就是普通的背包计数问题#include <cstdio>#include <cstring>int const MAXM = 1e5 + 5;int const MAXN = 1e2 + 5;bool dp[MAXM];int cnt[MAXM];int a[MAXN], c[MAXN];int main(){int n, m;while(scanf("%d %d", &n, &m) != EOF && (n + m)){memset(dp, false, sizeof(dp));for(int i = 1; i <= n; i ++)scanf("%d", &a[i]);for(int i = 1; i <= n; i ++)scanf("%d", &c[i]);dp[0] = true;int ans = 0;for(int i = 1; i <= n; i ++){memset(cnt, 0, sizeof(cnt));for(int s = a[i]; s <= m; s ++){if(!dp[s] && dp[s – a[i]] && cnt[s – a[i]] < c[i]){dp[s] = true;ans ++;cnt[s] = cnt[s – a[i]] + 1;}}}printf("%d\n", ans);}}
获致幸福的不二法门是珍视你所拥有的、遗忘你所没有的
