AC题解

#include<bits/stdc++.h>
using namespace std;
int N;
int v[25];
int G;
int f[15][25];
int s[15];
int p[25];
int minans;
int ha[15];
void input()
{
    cin>>N;
    for (int i=0;i<N;i++)
        cin>>v[i];
    cin>>G;
    for (int i=0;i<G;i++)
        for (int j=0;j<N;j++)
            cin>>f[i][j];
}
void dfs(int n)
{
    int ok=1; 
    for (int i=0;i<N;i++)
        if (p[i]<v[i])
        {
            ok=0;
            break;
        }
    if (ok)
    {
        int ans=0;
        for (int i=0;i<n;i++)
            ans+=s[i];
        if (ans<=minans)
        {
            minans=ans;
            memset(ha,0,sizeof(ha));
            for (int i=0;i<G;i++)
                if (s[i]==1) ha[i]=1;
        }
        return;
    }
    if (n==G) return;
    for (s[n]=0;s[n]<=1;s[n]++)
    {
        for (int i=0;i<N;i++)
            p[i]+=f[n][i]*s[n];
        dfs(n+1);
        for (int i=0;i<N;i++)
            p[i]-=f[n][i]*s[n];
    }
}
int main()
{
    input();
    minans=100000;
    dfs(0);
    cout<<minans;
    for (int i=0;i<G;i++)
        if  (ha[i]) cout<<' '<<i+1;
    cout<<endl;
    return 0;
}