題目1373魚塘釣魚(fishing題目描述有N個魚塘排成一排N100每個魚塘中有一定數(shù)量的魚例如N5時如下表魚塘編號每1分鐘能釣到的魚的數(shù)量1…1000每1分鐘能釣魚數(shù)的減少量1…100當(dāng)前魚塘到下一個相鄰魚塘需要的時間單位分鐘魚塘編號12345每1分鐘能釣到的魚的數(shù)量101420169每1分鐘能釣魚數(shù)的減少量24653當(dāng)前魚塘到下一個相鄰魚塘需要的時間單位分鐘3544即在第1個魚塘中釣魚第1分鐘內(nèi)可釣到10條魚第2分鐘內(nèi)只能釣到8條魚……第5分鐘以后再也釣不到魚了。從第1個魚塘到第2個魚塘需要3分鐘從第2個魚塘到第3個魚塘需要5分鐘……給出一個截止時間T(T1000)設(shè)計(jì)一個釣魚方案從第1個魚塘出發(fā)希望能釣到最多的魚。假設(shè)能釣到魚的數(shù)量僅和已釣魚的次數(shù)有關(guān)且每次釣魚的時間都是整數(shù)分鐘。輸入共5行分別表示第1行為N第2行為第1分鐘各個魚塘能釣到的魚的數(shù)量每個數(shù)據(jù)之間用一空格隔開第3行為每過1分鐘各個魚塘釣魚數(shù)的減少量每個數(shù)據(jù)之間用一空格隔開第4行為當(dāng)前魚塘到下一個相鄰魚塘需要的時間第5行為截止時間T。輸出一個整數(shù)不超過231?1表示你的方案能釣到的最多的魚。時空限制1s / 64MB樣例輸入5 10 14 20 16 9 2 4 6 5 3 3 5 4 4 14樣例輸出76思路y總按照前后反復(fù)橫跳可以將路線分為兩類一類是經(jīng)過某個點(diǎn)不釣魚接著回到這點(diǎn)釣魚后面到其他點(diǎn)釣之后再回到這個點(diǎn)釣魚。另一類是從第一個點(diǎn)徑直走到后面的點(diǎn)如果不再某點(diǎn)釣魚那么之后也不會返回再釣。由于釣魚的數(shù)量僅與釣魚時間有關(guān)所以第二類路線的釣魚數(shù)量第一類路線的釣魚數(shù)量。在第二類路線中可以細(xì)分為n條具體的路徑分別是從1-1從1-2從1-2-3…1-2-3…-n。枚舉每條具體的路徑求全局最優(yōu)。在每條路徑中假設(shè)該路徑從1-2-3-…m釣魚時間t總時間-路上花費(fèi)的時間。要想釣魚數(shù)量最大肯定希望每分鐘釣的魚數(shù)量最大。因此問題變成了求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;}結(jié)果