那種類(lèi)型的網(wǎng)站可以自己做也可以賺錢(qián)百度關(guān)鍵詞優(yōu)化推廣
有?N?個(gè)魚(yú)塘排成一排,每個(gè)魚(yú)塘中有一定數(shù)量的魚(yú),例如:N=5?時(shí),如下表:
魚(yú)塘編號(hào) | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
第1分鐘能釣到的魚(yú)的數(shù)量(1..1000) | 10 | 14 | 20 | 16 | 9 |
每釣魚(yú)1分鐘釣魚(yú)數(shù)的減少量(1..100) | 2 | 4 | 6 | 5 | 3 |
當(dāng)前魚(yú)塘到下一個(gè)相鄰魚(yú)塘需要的時(shí)間(單位:分鐘) | 3 | 5 | 4 | 4 |
即:在第?11?個(gè)魚(yú)塘中釣魚(yú)第?11?分鐘內(nèi)可釣到?1010?條魚(yú),第?22?分鐘內(nèi)只能釣到?88?條魚(yú),……,第?55?分鐘以后再也釣不到魚(yú)了。
從第?11?個(gè)魚(yú)塘到第?22?個(gè)魚(yú)塘需要?33?分鐘,從第?22?個(gè)魚(yú)塘到第?33?個(gè)魚(yú)塘需要?55?分鐘,……
給出一個(gè)截止時(shí)間?T,設(shè)計(jì)一個(gè)釣魚(yú)方案,從第?11?個(gè)魚(yú)塘出發(fā),希望能釣到最多的魚(yú)。
假設(shè)能釣到魚(yú)的數(shù)量?jī)H和已釣魚(yú)的次數(shù)有關(guān),且每次釣魚(yú)的時(shí)間都是整數(shù)分鐘。
輸入格式
共?55?行,分別表示:
第?11?行為?N;
第?22?行為第?11?分鐘各個(gè)魚(yú)塘能釣到的魚(yú)的數(shù)量,每個(gè)數(shù)據(jù)之間用一空格隔開(kāi);
第?33?行為每過(guò)?11?分鐘各個(gè)魚(yú)塘釣魚(yú)數(shù)的減少量,每個(gè)數(shù)據(jù)之間用一空格隔開(kāi);
第?44?行為當(dāng)前魚(yú)塘到下一個(gè)相鄰魚(yú)塘需要的時(shí)間;
第?55?行為截止時(shí)間?T。
輸出格式
一個(gè)整數(shù)(不超過(guò)2e9-1),表示你的方案能釣到的最多的魚(yú)。
數(shù)據(jù)范圍
1≤N≤100
1≤T≤1000
輸入樣例:
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
輸出樣例:
76
分析:
?利用貪心思維,并不需要來(lái)回折返,如果釣完一分鐘之后,這個(gè)魚(yú)塘的魚(yú)的數(shù)量依舊比其他魚(yú)塘多,那就繼續(xù)釣,這樣可以節(jié)省來(lái)回的路上時(shí)間,使時(shí)間最大化
?
注意:?
(1)int spend[N]={0};
(2)memset(spend,0,sizeof(spend));
兩個(gè)的區(qū)別:
第一行:
這行代碼是在定義數(shù)組時(shí)使用的,不是賦值操作,切記切記!!!
而且也只是給第一個(gè)數(shù)組賦值為0
第二行:
這個(gè)函數(shù)是C中的,作用是將spend數(shù)組全部賦值為0
#include<iostream>
#include<cstring>
using namespace std;
#define N 110int fishnum[N],d[N],dtime[N],spend[N];//魚(yú)數(shù),減少量,下個(gè)魚(yú)塘?xí)r間,釣魚(yú)所花時(shí)間int get(int k){//求出魚(yú)的數(shù)量return max(0,fishnum[k]-d[k]*spend[k]);
}int work(int n,int T){int res=0;memset(spend,0,sizeof(spend));//將spend數(shù)組全部賦值為0for(int i=0;i<T;i++){int t=1;for(int j=2;j<=n;j++){//從第二個(gè)開(kāi)始枚舉魚(yú)塘if(get(t)<get(j)){t=j;}}res+=get(t);//得到魚(yú)的總數(shù)量spend[t]++;}return res;
}
int main(){int n,T;cin>>n;for(int i=1;i<=n;i++) cin>>fishnum[i];for(int i=1;i<=n;i++) cin>>d[i];for(int i=2;i<=n;i++){cin>>dtime[i];dtime[i]+=dtime[i-1];//前綴和}cin>>T;int res=0;for(int i=1;i<=n;i++){res=max(res,work(i,T-dtime[i]));}cout<<res<<endl;return 0;}