by sx349
【摘要】
核心演算法思想：貪心
主要資料結構：
其他輔助知識：
時間複雜度：
空間複雜度：
【題目大意】
給定乙個非空矩陣，每次都從中選擇乙個最大值並將其從矩陣中排除，將這些取出的數排序後計算其花費（相鄰兩數的花費是其在矩陣之間的曼哈頓距離），求在給定最大花費下，能取到的最大值的最大總和。
【演算法分析】
文中說道：「你先找出花生最多的植株，去採摘它的花生；然後再找出剩下的植株裡花生最多的，去採摘它的花生；依此類推，不過你一定要在我限定的時間內回到路邊。」
根據這一句話，我們直接就可以得出，這道題應該採用貪心的演算法。
因此，我們先對資料進行從大到小的排序，然後每次都取其中的最大值。因為必須在規定的時間內回到路邊，所以在每次取最大值時，首先判斷在採摘了這一次之後是否有足夠的時間回到路邊，即(去採摘目標花生的時間)+(採摘那目標花生所用的1單位時間)+(從目標所在地往第一行的時間)<=(剩下的單位時間)。若條件不滿足就停止，若滿足就繼續採摘。
由於去摘花生必須從路邊進入花生田和從花生田出來，所以我們可以先減去2個單位時間，再將剩下的時間進行模擬。
【心得體會】
花生採摘是一道典型的貪心問題，也是一道典型的簡單題（因此這道題的演算法分析也只能這樣簡單了……）。但是這道題有乙個區別於其他問題的地方：在解決問題的過程中，主要部分（連續取最大值）的時間複雜度只需要，而排序卻花費了的時間複雜度。
這一點確實是在許多情況下無法迴避的乙個問題。我一直記得我們平時上課的計算機書上有乙個簡單的例子：給你一些**號碼，讓你去尋找某乙個指定的號碼。
書上的解釋是用二分查詢，但是我們來考慮一下，二分查詢合適嗎？當然，如果是在有序的情況下，二分的複雜度是，但是，在無序的情況下，二分必須要在排序好後才能解決，那麼時間複雜度就上公升到了，因為除了少部分特殊的排序之外，因此不可避免地導致了的排序複雜度。如此一來，就超過了順序查詢的複雜度了。
難道排序的合理性就此受到了質疑了嗎？當然不是，如果是查詢多次的話，二分查詢的時間複雜度就是，而順序查詢則飆公升到了。由此我們可以得出這樣乙個結論：
預處理操作的效率隨著預處理所得到的資料的使用率的提高而提高。
這又引出了這樣乙個怪異的想法：如果我找到了針對某個問題的乙個時間複雜度僅為的主演算法，那麼我是不是就一定能解決它呢？顯然不是。
如果這個問題的輸入達到了上千萬乃至上億，單單讀入的複雜度就已經使程式罷工了。同樣的，我也曾經有過因為輸出過多而導致超時的經歷。
因此，輸入、輸出、排序乃至其他一些游離於主演算法之外的東西，有時反而成為了乙個問題的決定點，這種出人意料的場景也著實是值得我們思考的。
【附錄】
【問題描述 】
魯濱遜先生有乙隻寵物猴，名叫多多。這天，他們兩個正沿著鄉間小路散步，突然發現路邊的告示牌上貼著一張小小的紙條：「歡迎免費品嚐我種的花生！——熊字」。
魯濱遜先生和多多都很開心，因為花生正是他們的最愛。在告示牌背後，路邊真的有一塊花生田，花生植株整齊地排列成矩形網路（如圖1）。有經驗的多多一眼就能看出，每株花生植株下的花生有多少。
為了訓練多多的算術，魯濱遜先生說：「你先找出花生最多的植株，去採摘它的花生；然後再找出剩下的植株裡花生最多的，去採摘它的花生；依此類推，不過你一定要在我限定的時間內回到路邊。」
我們假定多多在每個單位時間內，可以做下列四件事情中的一件：
1） 從路邊跳到最靠近路邊（即第一行）的某棵花生植株；
2） 從一棵植株跳到前後左右與之相鄰的另一棵植株；
3） 採摘一棵植株下的花生；
4） 從最靠近路邊（即第一行）的某棵花生植株跳回到路邊。
現在給定一塊花生田的大小和花生的分布，請問在限定的時間內，多多最多可以採到多少個花生？注意可能只有部分的植株下面長有花生，假設這些植株下的花生個數各不相同。
例如在圖二所示的花生田裡，只有位於（2，5），（3，7），（4，2），（5，4）的植株下長有花生，個數分別為13，7，15，9。沿著圖示的路線，多多在21個單位時間內，最多可以採到37個花生。
[輸入檔案]
輸入檔案peanuts.in的第一行包括三個整數，m，n和k，用空格隔開；表示花生田的大小為m*n（1<=m，n<=20），多多採花生的限定時間為k（0<=k<=1000）個單位時間.
接下來的m行,每行包括n個非負整數,也用空格隔開;
第i+1行的第j個整數pij(0<=pij<=500)表示花生田裡植株(i,j)下花生的數目,0表示該植株下沒有花生。
[輸出檔案]
輸出檔案peanuts.out包括一行.
這一行只包含乙個整數，即在限定時間內，多多最多可以採到的花生的個數。
[樣例輸入]
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
[樣例輸出1]
37[樣例輸入2]
6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
[樣例輸出2]
28【源程式清單】
program peanuts;
var x,y,value:array[0.400] of longint;
map:array[1..20,1..20] of longint;
m,n,k,i,j,top,t,sum:longint;
procedure sort(l,r:longint);
vari,j,mid:longint;
begin
i:=l;j:=r;mid:=value[(l+r) div 2];
repeat
while value[i]>mid do inc(i);
while value[j]if i<=j then begin
value[0]:=value[i];
value[i]:=value[j];
value[j]:=value[0];
x[0]:=x[i];x[i]:=x[j];x[j]:=x[0];
y[0]:=y[i];y[i]:=y[j];y[j]:=y[0];
inc(i);dec(j);
end;
until i>j;
if i if l end;
procedure print(k:longint);
begin
writeln(k);
halt;
end;
begin
read(m,n,k);
top:=0;
for i:=1 to m do
for j:=1 to n do begin
read(map[i,j]);
if map[i,j]<>0 then begin
inc(top);
value[top]:=map[i,j];
x[top]:=i;y[top]:=j;
end;
end;
sort(1,top);
k:=k-2;
x[0]:=1;y[0]:=y[1];
t:=0;i:=1;sum:=0;
while t t:=t+x[i]-x[i-1]+y[i]-y[i-1]+1;
if t+x[i]-1>k then print(sum);
sum:=sum+value[i];
t:=t+x[i]-1;
inc(i);
end;
end.
棉花生產實習報告
一 實驗目的 1.學習棉花主要植物學形態特徵。2.掌握棉花動態生長發育。3.掌握棉花產量形成過程 理論產量及田間實收產量的估測方法和考種方法。2 棉花的主要植物學形態特徵 1.根 棉花根系為直根系,呈倒圓錐形。直播棉花的主根上粗下細,主根入土深度因品種 土壤質地 結構 土層厚薄和水分狀況等環境條件不...
解題報告2 炸彈
藍貓炸彈 解題報告 1 題目描述 這天，藍貓2號來到了乙個實驗室，他正在對一排炸彈進行研究，這些炸彈排在一條直線上。為了方便，藍貓2號就把它們的位置用乙個數來表示，這個數就是這乙個炸彈與最左邊炸彈的距離，每乙個炸彈i都有乙個 威力值 si。如果藍貓2號直接引爆了乙個炸彈i，那麼它的威力就會向直線的兩...
銀鷺花生牛奶廣告效果評估調查問卷報告
小組成員 許慨 1009138 李偉 1009132 陳建奧 1009137 一 調查背景 廈門銀鷺食品 成立於1985年，主要從事罐頭食品以及飲料生產與加工，經過20年的發展，已經成為福建最大飲料生產基地，同時也是中國10大罐頭工業之一，2002年榮獲農業產業化國家重點龍頭企業，銀鷺品牌榮獲中國十...