修理牛棚  

2010-10-09 13:14:01|  分类： USACO-CHAPTER1|举报|字号 订阅

  下载LOFTER我的照片书  |

在一个夜黑风高,下着暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是供应商只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。 给出:可能买到的木板最大的数目M(1<= M<=50);牛棚的总数S(1<= S<=200); 牛棚里牛的总数C(1 <= C <=S);和牛所在的牛棚的编号stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度。 输出所需木板的最小总长度作为答案。 PROGRAM NAME: barn1 INPUT FORMAT: (file barn1.in) 1 行: M ， S 和 C(用空格分开)  2 到 C+1行:  每行包含一个整数，表示牛所占的牛棚的编号。OUTPUT FORMAT: (file barn1.out) 单独的一行包含一个整数表示所需木板的最小总长度。 SAMPLE INPUT4 50 183 4 6 8 1415 16 17 2125 26 27 30 31 40 41 42 43SAMPLE OUTPUT25[ 一种最优的安排是用板拦牛棚3-8,14-21,25-31,40-43.]

【分析】动归可解，贪心更直接。最少覆盖=全部覆盖-m-1个最大间隙【源程序】{ID:zhurui22LANG:PASCALTASK:barn1}Var cow,a:array[1..200]of integer;   m,s,c,i,j,k,y,ans:integer;Beginassign(input,'barn1.in');reset(input);assign(output,'barn1.out');rewrite(output);readln(m,s,c);for i:=1 to c do   readln(cow[i]);for i:=1 to c do   for j:=i+1 to c do      if cow[i]>cow[j] then      begin y:=cow[i];cow[i]:=cow[j];cow[j]:=y;end;for i:=1 to c do   if cow[i+1]-cow[i]-1>0 then   begin inc(k); a[k]:=cow[i+1]-cow[i]-1;end;for i:=1 to k do   for j:=i+1 to k do      if a[i]<a[j] then      begin y:=a[i];a[i]:=a[j];a[j]:=y;end;for i:=1 to m-1 do inc(ans,a[i]);writeln(cow[c]-cow[1]+1-ans);close(input);close(output);End.