USACO 2.1.4 Healthy Holsteins
題目連結:ofollow,noindex" target="_blank">http://train.usaco.org/usacoprob2?a=AIs2mu9dehf&S=holstein
思路:簡單搜尋。不沒次去累加而是相減看是否。
程式碼:
/* ID:zylbeyo1 LANG:C++ TASK:holstein */ #include <cstdio> #include <cctype> #include <cstring> #include <iostream> static const int MAXN=30; static const int MAXM=1050; static const int INF=1<<30; int n,m,num,ans=INF,cnt,a[MAXN],f[MAXM],s[MAXM][MAXN]; bool vis[MAXM]; inline int read() { int x=0;bool sign=false; char alpha=0; while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar(); while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar(); return sign?-x:x; } inline bool check() { for(int i=1;i<=n;i++) if(a[i]>0) return false; return true; } void dfs(int x) { if(check()) { if(cnt<ans) { num=0; ans=cnt; for(int i=1;i<=m;i++) if(vis[i]) f[++num]=i; return ; } } if(x>m) return ; for(int i=1;i<=n;i++) a[i]-=s[x][i]; vis[x]=true; cnt++; dfs(x+1); cnt--; for(int i=1;i<=n;i++) a[i]+=s[x][i]; vis[x]=false; dfs(x+1); } int main() { freopen("holstein.in","r",stdin); freopen("holstein.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i]=read(); m=read(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) s[i][j]=read(); dfs(1); printf("%d ",ans); for(int i=1;i<ans;i++) printf("%d ",f[i]); printf("%d\n",f[ans]); fclose(stdin); fclose(stdout); return 0; }