HDU 5527 Too Rich


题意:给出10张硬币,问如何凑出P¥且数量最多,无方案输出-1
思路:如果面值连续,后一个是前一个的倍数,从大往小凑,用小因子去凑更多的硬币,
但是本题存在$20,200$特殊处理这两种情况100¥折成250,500拆成5100,或200*2+100

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 22;
typedef long long ll;
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)

int a[maxn];
int b[maxn]={0,1,5,10,20,50,100,200,500,1000,2000};
ll sum[maxn];
int ans;
void solve(ll p, int idx, int cnt) {
    if(p < 0) return ;
    if(!idx && !p) { // finishit
        cmax(ans, cnt);
        return ;
    }
    ll rp = max(0LL, p-sum[idx-1]); //后面的凑完了,还要凑多少钱
    ll nc = rp / b[idx]; //当前的面值能凑几张
    if(rp % b[idx]) nc ++; // 
    if(nc <= a[idx]) solve(p-nc<em>b[idx],idx-1,cnt+nc); // 考虑np奇偶性
    if(nc+1 <= a[idx]) solve(p-(nc+1)</em>b[idx],idx-1,cnt+nc+1);
}
int main() {
    int t; scanf("%d", &t);
    while(t--) {
        int p;scanf("%d", &p);
        for(int i=1; i<=10; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i-1] + (ll)b[i] * a[i];
        }
        ans = -1;
        solve(p, 10, 0);
        printf("%d\n", ans);
    }
    return 0;
}

星星

当夜色降临
我站在台阶上倾听;
星星蜂拥在花园里
而我站在黑暗中。

听,一颗星星落地作响!
你别赤脚在这草地上散步,
我的花园到处是星星的碎片


KISS