題目1373魚塘釣魚(fishing題目描述有N個魚塘排成一排N100每個魚塘中有一定數量的魚例如N5時如下表魚塘編號每1分鐘能釣到的魚的數量1…1000每1分鐘能釣魚數的減少量1…100當前魚塘到下一個相鄰魚塘需要的時間單位分鐘魚塘編號12345每1分鐘能釣到的魚的數量101420169每1分鐘能釣魚數的減少量24653當前魚塘到下一個相鄰魚塘需要的時間單位分鐘3544即在第1個魚塘中釣魚第1分鐘內可釣到10條魚第2分鐘內只能釣到8條魚……第5分鐘以后再也釣不到魚了。從第1個魚塘到第2個魚塘需要3分鐘從第2個魚塘到第3個魚塘需要5分鐘……給出一個截止時間T(T1000)設計一個釣魚方案從第1個魚塘出發希望能釣到最多的魚。假設能釣到魚的數量僅和已釣魚的次數有關且每次釣魚的時間都是整數分鐘。輸入共5行分別表示第1行為N第2行為第1分鐘各個魚塘能釣到的魚的數量每個數據之間用一空格隔開第3行為每過1分鐘各個魚塘釣魚數的減少量每個數據之間用一空格隔開第4行為當前魚塘到下一個相鄰魚塘需要的時間第5行為截止時間T。輸出一個整數不超過231?1表示你的方案能釣到的最多的魚。時空限制1s / 64MB樣例輸入5 10 14 20 16 9 2 4 6 5 3 3 5 4 4 14樣例輸出76思路y總按照前后反復橫跳可以將路線分為兩類一類是經過某個點不釣魚接著回到這點釣魚后面到其他點釣之后再回到這個點釣魚。另一類是從第一個點徑直走到后面的點如果不再某點釣魚那么之后也不會返回再釣。由于釣魚的數量僅與釣魚時間有關所以第二類路線的釣魚數量第一類路線的釣魚數量。在第二類路線中可以細分為n條具體的路徑分別是從1-1從1-2從1-2-3…1-2-3…-n。枚舉每條具體的路徑求全局最優。在每條路徑中假設該路徑從1-2-3-…m釣魚時間t總時間-路上花費的時間。要想釣魚數量最大肯定希望每分鐘釣的魚數量最大。因此問題變成了求m個序列中的前t大元素。可以用大根堆來做。代碼#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN10010;intn,fish[N],sub[N],tim[N],T,ans;intwork(intm){intfishtimT-tim[m];priority_queuePIIheap;for(inti1;im;i)heap.push({fish[i],i});intk0,sum0;while(!heap.empty()kfishtim){PII theap.top();heap.pop();sumt.first;intit.second;if(t.first-sub[i]0)heap.push({t.first-sub[i],i});k;}returnsum;}intmain(){cinn;for(inti1;in;i)cinfish[i];for(inti1;in;i)cinsub[i];for(inti2;in;i){cintim[i];tim[i]tim[i-1];}cinT;for(inti1;in;i)ansmax(ans,work(i));coutans;return0;}結果