USACO milk4 枚举答案再检验

刚开始写了一个暴力的dfs超时了， 最后看了下题解说是先枚举答案再判断，然后就写了双dfs，全部秒杀，代码如下：

/*
    ID: m1500293
    LANG: C++
    PROG: milk4
*/
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
int Q, P;
int t[110];

bool dfs1(int dept, int a[], int num, int rQ)
{
    if(rQ==0) return true;
    if(dept==num) return false;
    bool res = false;
    for(int i=1; i<=Q/a[dept]; i++)
    {
        if(rQ-a[dept]*i >= 0)
            res = res || dfs1(dept+1, a, num, rQ-a[dept]*i);
    }
    return res;
}
bool flog;
void dfs(int dept, int a[], int num, int nn)
{
    if(flog) return ;
    if(num > nn) return;
    if(num == nn)
    {
        if(dfs1(0, a, num, Q))
        {
            printf("%d ", num);
            for(int i=0; i<num; i++)
                printf("%d%c", a[i], i==num-1?'\n':' ');
            flog = true;
        }
        return ;
    }
    if(dept == P) return;
    a[num] = t[dept];
    dfs(dept+1, a, num+1, nn);
    dfs(dept+1, a, num, nn);
}
bool cmp(const int &a, const int &b)
{
    return a<b;
}
int main()
{
    freopen("milk4.in", "r", stdin);
    freopen("milk4.out", "w", stdout);
    scanf("%d%d", &Q, &P);
    for(int i=0; i<P; i++) scanf("%d", &t[i]);
    sort(t, t+P, cmp);
    int a[110];
    flog = false;
    for(int i=1; i<=P&&!flog; i++)
    {
        dfs(0, a, 0, i);
    }
    return 0;
}

原文链接: https://www.cnblogs.com/xingxing1024/p/5180632.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍