poj 1742

Coins

Silverland的人使用硬币。他们有A1，A2，A3的硬币…一个Silverland美元。一天，Tony打开他的存钱罐，发现里面有一些硬币。他决定在附近的商店里买一块非常漂亮的手表。

他想付确切的价格（没有零钱），他知道价格不会超过m。但是他不知道手表的确切价格。

您将要编写一个程序，该程序读取n，m，A1，A2，A3 … An和C1，C2，C3 … Cn对应于托尼硬币的值A1，A2，A3 …的数量，然后
计算托尼可以使用这些硬币支付多少价格（从1到m）

输入值

输入包含几个测试用例。

每个测试用例的第一行包含两个整数n（1 <= n <= 100），m（m <=
100000）。第二行包含2n个整数，分别表示A1，A2，A3 … An，C1，C2

，C3 … Cn（1 <= Ai <= 100000,1 <= Ci <= 1000）。

最后一个测试用例后跟两个零。

输出量

对于每个测试用例，在一行上输出答案。

样本输入

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

样本输出
8
4

题意
n个物体，第i个物体有Ci个, 价值为Ai，取出的和小于等于m 的 种类数

（1）用多重背包做

//时间复杂度过大，即使快读也会T
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>const int MAXM = 1e5 + 5;
int dp[3][MAXM], a[MAXM];using namespace std;
int main() {
    int n, m;while(scanf("%d%d", &n, &m) != EOF) {
    if(n == 0 && m == 0) break;int A[103], C[103];memset(dp, 0 ,sizeof(dp));memset(a, 0 ,sizeof(a));int cnt = 0;for (int i = 0; i < n; i++) scanf("%d", &A[i]);for (int i = 0; i < n; i++) {
    scanf("%d", &C[i]);int ss = 1;while(C[i] >= ss) {
    a[cnt++] = A[i] * ss;C[i] -= ss;ss <<= 1;}if(C[i] > 0) {
    a[cnt++] = C[i] * A[i];}}int L;//dp[L][j]储存了j元是最多能拿多少钱，如果全部拿完时为Q元(j = jq)，则j > jq，dp[L][j]都为Q元，则减去重复数则为种类数for (int i = 0; i < cnt; i++) {
    for (int j = 0; j <= m; j++) {
    L = i & 1;dp[L][j] = dp[L ^ 1][j];if(j >= a[i]) {
    dp[L][j] = max(dp[L ^ 1][j - a[i]] + a[i], dp[L][j]);}}}long long ans = m;for (int i = 0; i < m; i++) {
    if(dp[L][i + 1] == dp[L][i]) ans--;//cout <<i << " " << dp[L][i] << endl;} printf("%lld\n", ans);}
}

（2）优化

//O(nm)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>const int MAXM = 1e5 + 5;
int dp[MAXM], A[103], C[103];
int n, m;using namespace std;
int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
    if(n == 0 && m == 0) break;memset(dp, -1 ,sizeof(dp));for (int i = 0; i < n; i++) scanf("%d", &A[i]);for (int i = 0; i < n; i++) scanf("%d", &C[i]);dp[0] = 0;for (int i = 0; i < n; i++) {
    for(int j = 0; j <= m; j++) {
    if(dp[j] >= 0) dp[j] = C[i];else if(j < A[i] || dp[j - A[i]] <= 0) dp[j] = -1;else dp[j] = dp[j - A[i]] - 1;}}long long ans = 0;for (int i = 1; i <= m; i++)if(dp[i] != -1) ans++;printf("%lld\n", ans);}
}