Description

　　農(nóng)民JOHN以擁有世界上最健康的奶牛為驕傲。他知道每種飼料中所包含的的牛所需的最低的維他命量是多少。請你幫助農(nóng)夫喂養(yǎng)他的牛，以保持他們的健康，使喂給牛的飼料的種數(shù)最少。
　　給出牛所需的最低的維他命，輸出喂給牛需要哪些種類的飼料，且所需的種類數(shù)最少。

Input

第1行：一個整數(shù)V(1<=V<=25)，表示需要的維他命的種類數(shù)。
第2行：V個整數(shù)(1<=每個數(shù)<=1000)，表示牛每天需要的維他命的最小量。
第3行：一個整數(shù)G(1<=G<=15)，表示可用來喂牛的飼料的數(shù)量。下面G行，第i行表示編號為i飼料包含的各種維他命的量的多少。

Output

輸出文件只有一行，包括：
? 牛必需的最小的飼料種數(shù)P
? 后面有P個數(shù)，表示所選擇的飼料編號（按從小到大排列）。
末尾有空行

題解

就一個dfs，水了。
Executing…
Test 1: TEST OK [0.000 secs, 340 KB]
Test 2: TEST OK [0.000 secs, 340 KB]
Test 3: TEST OK [0.000 secs, 340 KB]
Test 4: TEST OK [0.000 secs, 340 KB]
Test 5: TEST OK [0.000 secs, 340 KB]
Test 6: TEST OK [0.000 secs, 340 KB]
Test 7: TEST OK [0.000 secs, 340 KB]
Test 8: TEST OK [0.000 secs, 340 KB]
Test 9: TEST OK [0.011 secs, 340 KB]
Test 10: TEST OK [0.011 secs, 340 KB]
All tests OK.

代碼

{ ID: zyx52yzl LANG: PASCAL TASK: holstein } varm,n,l,tot,min:longint;a:array [0..31]of longint;ans,tmp:array [0..20]of longint;f:array [0..20,0..31] of longint; procedure init; vari,j:longint; beginreadln(n);for i:=1 to n doread(a[i]);readln(m);for i:=1 to m dofor j:=1 to n doread(f[i,j]);tot:=0;min:=maxlongint; end;function check:boolean; vari:longint; beginfor i:=1 to n doif a[i]>0 then exit(false);exit(true); end;procedure dfs(k:longint); vari:longint; beginif (check) and (tot<min) thenbeginans:=tmp;min:=tot;end;if k>m then exit;inc(tot);tmp[tot]:=k;for i:=1 to n doa[i]:=a[i]-f[k,i];dfs(k+1);dec(tot);for i:=1 to n doa[i]:=a[i]+f[k,i];dfs(k+1); end;procedure print; vari:longint; beginwrite(min,' ');for i:=1 to min-1 dowrite(ans[i],' ');writeln(ans[min]); end;beginassign(input,'holstein.in');assign(output,'holstein.out');reset(input);rewrite(output);init;dfs(1);print;close(input);close(output); end.

轉(zhuǎn)載于:https://www.cnblogs.com/zyx-crying/p/9319561.html

總結(jié)

以上是生活随笔為你收集整理的USACO 2.1 健康的好斯坦奶牛 (DFS)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。