POJ 1742【存疑】

==>原题链接

题目概述

有面值为A1，A2，A3...An的钱C1，C2，C3...Cn张，给定一个范围M，问这些钱可以组成的面值数。

思路

这个写的挺好的。

DP。状态转移方程

if (!dp[j] && (cnt[j-value[i]] < num[i]) && dp[j-value[i]])
{

   ans++;
   dp[j] = true;
   cnt[j] = cnt[j-value[i]] + 1;

}

其中dp[j]表示金额 j 是否可以取到。dp[j]依赖于dp[j-value]即假定这种面值被取到，那么须之前的面值可被取到。
cnt[j]表示得到 j 面额需要 i 的张数。由三重循环降维到两重， 就可以过了。

参考分量太多，MARK，稍后思考。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100 + 10,
          M = 100000 + 10;

int value[N], num[N], cnt[M];
bool dp[M];


int main()
{
    int i, j;
    int n, m, ans;

    freopen("1742.in", "r", stdin);
    while(~scanf("%d%d", &n, &m) && n != 0 && m != 0)
    {
        for (i = 0; i < n; i++)
        {
            scanf("%d", &value[i]);
        }
        for (i = 0; i < n; i++)
        {
            scanf("%d", &num[i]);
        }

        ans = 0;
        memset(dp, false, sizeof(dp));
        dp[0] = true;
        for (i = 0; i < n; i++)
        {
            memset(cnt, 0, sizeof(cnt));
            for (j = value[i]; j <= m; j++)
            {
                if (!dp[j] && (cnt[j-value[i]] < num[i]) && dp[j-value[i]])
                {
                    ans++;
                    dp[j] = true;
                    cnt[j] = cnt[j-value[i]] + 1;
                }
            }
        }

        printf("%d\n", ans);

    }

    return 0;
}