url: https://www.luogu.com.cn/problem/P2851

tag:
动态规划，背包DP，进制，USACO，2006

思路：
可以用背包来做。用 f[i] 表示john付i块钱时最少的硬币数，用 g[i] 表示店主找零i块钱时最少的硬币数，对于f来说，因为硬币数量有限所以需要用多重背包来完成。而对于g来说因为硬币无限多，所以可以用完全背包。对于体积上限取多少可以参考： https://www.luogu.com.cn/article/sd0bx6un

代码：

#include <iostream>  
#include <cstring>  
#include <cstdio>  
#include <algorithm>  
using namespace std;  
typedef long long LL;  
const int N = 10010, M = 150;  
int c[M], v[M];  
int f[N + M * M], g[N + M * M];  
int n, t, mx, sum;  
int main()  
{  
    cin >> n >> t;  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> v[i];  
        mx = max(mx, v[i] * v[i]);  
    }  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> c[i];  
        sum += v[i] * c[i];  
    }  
    if (sum < t)  
    {  
        cout << -1 << endl;  
        return 0;  
    }  
    memset(f, 0x3f, sizeof f);  
    memset(g, 0x3f, sizeof g);  
    g[0] = 0;  
    f[0] = 0;  
    for (int i = 1; i <= n; i ++)  
        for (int j = v[i]; j <= mx; j ++)  
            g[j] = min(g[j], g[j - v[i]] + 1);  
    for (int i = 1; i <= n; i ++)  
    {  
        for (int j = 1; j <= c[i]; j *= 2)  
        {  
            for (int k = mx + t; k >= j * v[i]; k --)  
                f[k] = min(f[k], f[k - j * v[i]] + j);  
            c[i] -= j;  
        }  
        if (c[i])  
            for (int k = mx + t; k >= c[i] * v[i]; k --)  
                f[k] = min(f[k], f[k - c[i] * v[i]] + c[i]);  
    }  
    int res = 0x3f3f3f3f;  
    for (int i = t; i <= t + mx; i ++)  
        res = min(res, f[i] + g[i - t]);  
    cout << (res == 0x3f3f3f3f ? -1 : res) << endl;  
    return 0;  
}