USACO Dec2011 Bronze: Escaping the Farm 翻譯+題解

Problem 3: Escaping the Farm [Brian Dean and Kalki Seksaria, 2011]
【英文原題】
The cows have decided on a daring plan to escape from the clutches of
Farmer John. They have managed to procure a small inflatable raft, and
during the cover of night, a group of cows will board the raft and row
across the river bordering the farm. The plan seems perfect, until the
cows realize that their small inflatable raft may not be able to hold
much weight!
The N cows (1 group of cows is light enough to avoid sinking the raft, the cows add up
all of the weights in the group. Unfortunately, cows are notoriously bad at
arithmetic, and if the addition of the weights of the cows in a group
causes any carries to occur (using standard base 10 addition), then the
cows give up and conclude that group must weigh too much to use the raft.
Any group whose weights can be added without any carries is assumed to be
light enough to fit on the raft.
Please help the cows determine the size of the largest group that they
believe can fit on the raft (that is, the largest group whose weights can
be added together with no carries).
PROBLEM NAME: escape
INPUT FORMAT:
* Line 1: The number of cows, N (1
* Lines 2..N+1: Each line contains the weight of one cow, an integer
in the range 1…100,000,000.
SAMPLE INPUT (file escape.in):
5
522
6
84
7311
19
INPUT DETAILS:
There are 5 cows, with weights 522, 6, 84, 7311, and 19.
OUTPUT FORMAT:
* Line 1: The number of cows in the largest group whose weights can be
added together with no carries.
SAMPLE OUTPUT (file escape.out):
3
OUTPUT DETAILS:
The three weights 522, 6, and 7311, can be added together with no carries:
522
6
+ 7311
——
7839

【中文翻譯】

Problem 3:逃離農場
譯by Freddy
【題目描述】
奶牛們做了一個魯莽的計劃：那就是逃離農場主Farmer John。她們已經獲得了一個可充氣的小型木筏，計劃在某天夜晚中，一群奶牛通過使用木筏渡而過位於農場邊界的河流。這個計劃似乎很完美，直到奶牛們意識到她們的小木筏可能不能承受住她們的體重。

這N頭奶牛(1<=N<=20)的體重w_1…w_N。為了計算出一群奶牛的體重能否避免木筏沉沒的悲劇，一群奶牛把她們的體重加在一起。
不幸的是，奶牛們在算術方面臭名遠揚，並且一群奶牛內的各奶牛體重相加的過程中如果出現了進位（標準的10進制），那麼這群奶牛只好放棄因為她們知道她們的體重對於小木筏來說太重了。

所有 那些群內奶牛體重相加不出現進位的奶牛群都被認為可以乘坐那個木筏而不發生沉沒。

請幫奶牛們找出能乘坐木筏而不沉沒的奶牛群的最大奶牛數。（也就是說，找出最多的奶牛使她們的體重相加而不出現進位。）

程序名：escape
輸入格式：
▪第1行：奶牛的數量，N(1<=N<=20)
▪第2…N+1行：每行包含一頭奶牛的體重，一個整數(1…100,000,000)。
輸入樣例(file escape.in)：
5
522
6
84
7311
19
輸入解釋：
有5只奶牛，她們的體重分別為522，6，84，7311和19。
輸出格式：
只有一行，表示一群使她們的體重相加而不出現進位的奶牛的最大奶牛數量。
輸出樣例（file escape.out）：
3
輸出解釋：



這三個奶牛的體重分別為：522，6，7311，它們相加不會出現進位：
    522
       6
+7311
 ——–
  7839

【分析】
搜索題目，可以用DFS。遞歸每頭牛的兩種狀態：要或者不要，每次遞歸判斷一下是否符合要求（沒有進位），然後更新最優值即可。
時間複雜度:
DFS遞歸：O(2^N)
判斷：O(KN) 『K是讀入的數字的平均長度，根據題意，可取5～6』

【我的代碼】

/*
ID:yeefan
LANG:C++
PROB:escape
website:http://yeefan.tk/
*/
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
int N;
int W[21];
int A=0;
int Q[21];
int Best=0;
void init()
{
 scanf("%d\n",&N);
 for (int i=1;i<=N;i++)
  scanf("%d\n",&W[i]);
 return;
}
void check()
{
 int T[11];
 memset(T,0,sizeof(T));
 for(int i=1;i<=A;i++)
 {
  int K=1;
  int tmp=W[Q[i]];
  while(tmp!=0)
  {
   T[K]+=tmp%10;
   tmp/=10;
   K++;
  }
 }
 for(int i=1;i<=10;i++)
 {
  if(T[i]>=10)
   return;
 }
 if(A>Best)
  Best=A;
}
void dfs(int num)
{
 if(num==N+1)
 {
  check();
  return;
 }
 Q[++A]=num;
 dfs(num+1);
 A--;
 dfs(num+1);
}
int main()
{
 freopen("escape.in","r",stdin);
 freopen("escape.out","w",stdout);
 init();
 dfs(1);
 printf("%d\n",Best);
 //printf("%d\n",clock());
 return 0;
}