题解 P2851 【[USACO06DEC]The Fewest Coins G】

· · 题解

题

官方题解中提到找零数的上界是 v_{max}^2，但是并没有给出证明，我目前也不会证。
这里给出了找零数 \leq 2\times v_{max}^2 的证明。

首先一个显然的思路，枚举找零的量 x，那么付钱的量就是 x+T，找零是完全背包（硬币数无限），付钱是多重背包（硬币数有限），注意多重背包要二进制分组优化或者单调队列优化，这里不详细展开了。

看到这里有一个问题，这个 x 最大要枚举到多少？
直观感受下，这个 x 并不会特别大。
实际上，如果面值最大的币面值为 v_{max}，x\leq 2\times v_{max}^2，下面给出证明。

反证，如果 >v_{max}，那么一定能找出一些硬币，它们的面值之和 v_{max} 的倍数，可以替换成若干个面值最大的币，使得硬币总数减少。把这些硬币排成一排，面值形成一个序列 a_i，对这个序列做前缀和 pre_i，区间和等于前缀和作差，在大于 v_{max} 个前缀和中，根据抽屉原理，必然存在两个 pre_i 除以 v_{max} 余数相同，假设它们为 pre_i 和 pre_j(0\leq i<j)，那么 [i+1,j] 这段区间和是 v_{max} 的倍数。

接下来分类讨论。

这里先说明一下，下面的过程都是按在付钱部分和找零部分中不断同时删去一些面值之和相等的硬币，直到按该方法无法再删去任何硬币为止分析的。

显然，此时付钱中不能有面值最大的币了，否则可以两边各删一个硬币，直到付钱中没有或者找零中没有为止。

所以付钱中所有的钱都不是面值最大的币，那么如果付钱中硬币的数量小于 v_{max}，付钱就小于 v_{max}^2 找零自然就小于 v_{max}^2 了。如果付钱的硬币多于 v_{max} 个，那么可以从中选出 v_{max}+1 个硬币，根据上文的分析，在选出的硬币中一定存在一些硬币，它们的面值之和是 v_{max} 的倍数，我们并不知道具体是几倍，但是这个倍数一定 \leq v_{max}（因为 v_{max}+1 个面值小于 v_{max} 的硬币面值之和不可能大于等于 (v_{max}+1)\times v_{max}）。这里可以得出找零中最多只有 v_{max}-1 个面值最大的币，否则可以替换。

找零中面值最大的币少于 v_{max} 个，面值非最大的币最多有 v_{max} 个，所以找零总量小于 2\times v_{max}^2

很明显，找零小于 v_{max}^2

所以，在 x\geq2\times v_{max}^2 的时候，一定可以通过一些方式把交流的硬币总数减少，直到 x<2\times v_{max}^2 为止。

代码： 

using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL V = 28800; // 2 * v_{max}^2

LL n,t;
LL v[105],c[105];
LL dp1[V << 1],dp2[V << 1]; // 这里我直接 2V 了，其实 V+t 就够
LL ans = INF;

int main(){
    memset(dp1,INF,sizeof(dp1));
    memset(dp2,INF,sizeof(dp2));
    cin >> n >> t;
    for(LL i = 1;i <= n;i ++) cin >> v[i];
    for(LL i = 1;i <= n;i ++) cin >> c[i];
    dp1[0] = dp2[0] = 0;

    for(LL i = 1;i <= n;i ++)
        for(LL j = v[i];j <= V;j ++) dp2[j] = min(dp2[j],dp2[j - v[i]] + 1);
    for(LL i = 1;i <= n;i ++){
        for(LL w = 1;w <= c[i];w <<= 1){
            for(LL j = V + t;j >= v[i] * w;j --) dp1[j] = min(dp1[j],dp1[j - v[i] * w] + w);
            c[i] -= w;
        }
        if(c[i]) for(LL j = V + t;j >= v[i] * c[i];j --) dp1[j] = min(dp1[j],dp1[j - v[i] * c[i]] + c[i]);
    }
    for(LL i = t;i <= t + V;i ++) ans = min(ans,dp1[i] + dp2[i - t]);
    if(ans >= INF) ans = -1;
    cout << ans << '\n';
    return 0;
}