男人八题

男人八题

寒假的时候在一博客上看到楼教主的男人八题，乃是经典中的经典，当时看了AC率最高的一题，妈的，多重背包，GG = =，今天再看看这套题，记录下一个男人的成长过程= =

POJ 1742

题意

n种面值Ai不同的硬币，分别有Ci个，问能凑成多少种小于等于m的价值。（1<=n<=100，m<=100000，1<=Ai<=100000，1<=Ci<=1000）

思路

看完题，就往多重背包上套，这一题的数据范围实在可怕
dp[i][j] 表示用前i种硬币能否凑成j，然后三重循环递推

const int maxn = 105;
const int maxm = 100005;
bool dp[maxn][maxm];
int coin[maxn], num[maxn];
int n, m;
int main() {
    while (~scanf("%d %d", &n, &m)) {
        if (n == 0 && m == 0) break;
        memset(dp, false, sizeof(dp));
        for (int i = 1; i <= n; i ++) scanf("%d", &coin[i]);
        for (int i = 1; i <= n; i ++) {
            scanf("%d", &num[i]);
            for (int j = 1; j <= num[i]; j ++) {
                if (coin[i] * j <= m) dp[i][coin[i]*j] = true;
            }
        }
        for (int i = 2; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                dp[i][j] |= dp[i-1][j];
                for (int k = 1; k <= num[i]; k ++) {
                    if (j >= coin[i] * k) dp[i][j] |= dp[i-1][j-(coin[i]*k)];
                    else break;
                }
            }
        }
        int ans = 0;
        for (int j = 1; j <= m; j ++) {
            if (dp[n][j]) ans ++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

复杂度：O(m∑iCi)
想都不用想，华丽丽的超时，卡题的感觉真是崩溃啊 ToT

剪枝！剪枝！！剪枝！！！

优化dp定义：

1. dp[i][j] 表示 用前i种硬币凑成j时第i种硬币最多能剩余多少个（-1表示配不出来）
   如果dp[i - 1][j] >= 0(前i-1个数可以凑出j，那么第i个数根本用不着)直接为C[i]
2. dp[i][j] = -1 :如果j < A[i]或者dp[i][j - a[i]] <=0 (面额太大或者在配更小的数的时候就用光了）
   = dp[i][j-a[i]] - 1 其他（将第i个数用掉一个）
   最后统计一下dp数组第n行>=0的个数就知道答案了

const int maxn = 105;
const int maxm = 100005;
int dp[maxn][maxm];
int coin[maxn], num[maxn];
int n, m;
int main() {
    while (~scanf("%d %d", &n, &m)) {
        if (n == 0 && m == 0) break;
        for (int i = 1; i <= n; i ++) scanf("%d", &coin[i]);
        for (int i = 1; i <= n; i ++) scanf("%d", &num[i]);
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        for (int i = 0; i < n; i ++) {
            dp[i+1][0] = num[i+1];
            for (int j = 1; j <= m; j ++) {
                if(dp[i][j] >= 0) dp[i+1][j] = num[i+1];
                else if (j < coin[i+1] || dp[i+1][j-coin[i+1]] <= 0) dp[i+1][j] = -1;
                else dp[i+1][j] = dp[i+1][j-coin[i+1]] - 1;
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; i ++) {
            if (dp[n][i] >= 0) ans ++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

楼教主真是神啊，好像知道我要这么写啊，擦，又MLE了，，，真不愧是神题啊 TOT

然后发现数组其实是重复利用的，所以大可不必开二维，最后AC代码：

const int maxn = 105;
const int maxm = 100005;
int dp[maxm];
int coin[maxn], num[maxn];
int n, m;
int main() {
    while (~scanf("%d %d", &n, &m)) {
        if (n == 0 && m == 0) break;
        for (int i = 1; i <= n; i ++) scanf("%d", &coin[i]);
        for (int i = 1; i <= n; i ++) scanf("%d", &num[i]);
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        for (int i = 0; i < n; i ++) {
            dp[0] = num[i+1];
            for (int j = 1; j <= m; j ++) {
                if(dp[j] >= 0) dp[j] = num[i+1];
                else if (j < coin[i+1] || dp[j-coin[i+1]] <= 0) dp[j] = -1;
                else dp[j] = dp[j-coin[i+1]] - 1;
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; i ++) {
            if (dp[i] >= 0) ans ++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

仅此一题，对楼教主佩服的真是五体投地。。。后面还有七题等着去征服= =