USACO sec2.1 Healthy Holsteins

ステータス圧縮は、生成されたすべてのステータスをソートし、列挙すればよい.

/*

PROG : holstein

LANG : C

*/

# include <stdio.h>

# include <stdlib.h>



struct scoop{int a[30];};



int V, G, r[(1 << 17) + 5];

struct scoop g[17], v;



/***************************************************/

int bcnt(int x)

{

    int ret = 0;

    while (x)

    {

        ++ret;

        x &= x-1;

    }

    return ret;

}



int cmp(const void *xx, const void *yy)

{

    int x = *(int*)xx;

    int y = *(int*)yy;

    int t = bcnt(x) - bcnt(y);

    if (t == 0) return x>y ? 1:-1;

    return t;

}



void pre(void)

{

    int i;

    for (i = 0; i < (1<<(G+1)); ++i) r[i] = i;

    qsort(r, (1<<(G+1)), sizeof(r[1]), cmp);

}



int cal(int x)

{

    int i, j;

    struct scoop tmp = v;

    for (i = 0; i < G; ++i) if ((x>>i) & 0x1)

    for (j = 1; j <= V; ++j)

        tmp.a[j] -= g[i+1].a[j];

    for (j = 1; j <= V; ++j)

        if (tmp.a[j] > 0) return 0;

    return 1;

}



void solve(void)

{

    int i, k;

    pre();

    for (i = 0; i < (1<<(G+1)); ++i)

        if (cal(r[i])) break;

    printf("%d", bcnt(r[i]));

    for (k = 0; k < G; ++k) if ((r[i]>>k)&0x1)

        printf(" %d", k+1);

    putchar('
');

}

/***************************************************/



void read(void)

{

    int i, j;

    scanf("%d", &V);

    for (i = 1; i <= V; ++i) scanf("%d", &v.a[i]);

    scanf("%d", &G);

    for (i = 1; i <= G; ++i)

    for (j = 1; j <= V; ++j)

        scanf("%d", &g[i].a[j]);

}



int main()

{

    freopen("holstein.in", "r", stdin);

    freopen("holstein.out", "w", stdout);



    read();

    solve();



    fclose(stdin);

    fclose(stdout);



    return 0;

}

DFSは間違いなくタイムアウトします.