星期二下午，駕駛學(xué)科奧賽培訓(xùn)。
沈笑夫才知道，江岸市第一職業(yè)中學(xué)一年級參加駕駛學(xué)科奧賽培訓(xùn)的共有20人。
王老師親自上課。首先讓大家自我介紹，互相認(rèn)識了一下。
20個(gè)同學(xué)，男生占了15個(gè)，女生僅僅5個(gè)，少得可憐！
沈笑夫翻閱《高中組駕駛學(xué)科奧賽基礎(chǔ)知識》，覺得比初中組難了不少。
王老師說，今天學(xué)習(xí)的是程序——《道路游戲》。
【題目描述】
小新正在玩一個(gè)簡單的電腦道路游戲。
游戲中有一條環(huán)形馬路，馬路上有 n 個(gè)機(jī)器人工廠，兩個(gè)相鄰機(jī)器人工廠之間由一小段馬路連接。
小新以某個(gè)機(jī)器人工廠為起點(diǎn)，按順時(shí)針順序依次將這 n 個(gè)機(jī)器人工廠編號為1~n，因?yàn)轳R路是環(huán)形的，所以第 n 個(gè)機(jī)器人工廠和第 1 個(gè)機(jī)器人工廠是由一段馬路連接在一起的。
小新將連接機(jī)器人工廠的這 n 段馬路也編號為 1~n，并規(guī)定第 i 段馬路連接第 i 個(gè)機(jī)器人工廠和第 i+1個(gè)機(jī)器人工廠（1≤i≤n-1），第 n 段馬路連接第n個(gè)機(jī)器人工廠和第 1個(gè)機(jī)器人工廠。
游戲過程中，每個(gè)單位時(shí)間內(nèi)，每段馬路上都會出現(xiàn)一些金幣，金幣的數(shù)量會隨著時(shí)間發(fā)生變化，即不同單位時(shí)間內(nèi)同一段馬路上出現(xiàn)的金幣數(shù)量可能是不同的。
小新需要機(jī)器人的幫助才能收集到馬路上的金幣。
所需的機(jī)器人必須在機(jī)器人工廠用一些金幣來購買，機(jī)器人一旦被購買，便會沿著環(huán)形馬路按順時(shí)針方向一直行走，在每個(gè)單位時(shí)間內(nèi)行走一次，即從當(dāng)前所在的機(jī)器人工廠到達(dá)相鄰的下一個(gè)機(jī)器人工廠，并將經(jīng)過的馬路上的所有金幣收集給小新。
例如，小新在 i（1≤i≤n）號機(jī)器人工廠購買了一個(gè)機(jī)器人，這個(gè)機(jī)器人會從 i 號機(jī)器人工廠開始，順時(shí)針在馬路上行走，第一次行走會經(jīng)過 i 號馬路，到達(dá) i+1 號機(jī)器人工廠（如果 i=n，機(jī)器人會到達(dá)第 1 個(gè)機(jī)器人工廠），并將 i 號馬路上的所有金幣收集給小新。
游戲中，環(huán)形馬路上不能同時(shí)存在2個(gè)或者2個(gè)以上的機(jī)器人，并且每個(gè)機(jī)器人最多能夠在環(huán)形馬路上行走 p次。
小新購買機(jī)器人的同時(shí)，需要給這個(gè)機(jī)器人設(shè)定行走次數(shù)，行走次數(shù)可以為 1~p 之間的任意整數(shù)。當(dāng)馬路上的機(jī)器人行走完規(guī)定的次數(shù)之后會自動消失，小新必須立刻在任意一個(gè)機(jī)器人工廠中購買一個(gè)新的機(jī)器人，并給新的機(jī)器人設(shè)定新的行走次數(shù)。
以下是游戲的一些補(bǔ)充說明：
游戲從小新第一次購買機(jī)器人開始計(jì)時(shí)。
購買機(jī)器人和設(shè)定機(jī)器人的行走次數(shù)是瞬間完成的，不需要花費(fèi)時(shí)間。
購買機(jī)器人和機(jī)器人行走是兩個(gè)獨(dú)立的過程，機(jī)器人行走時(shí)不能購買機(jī)器人，購買完機(jī)器人并且設(shè)定機(jī)器人行走次數(shù)之后機(jī)器人才能行走。
在同一個(gè)機(jī)器人工廠購買機(jī)器人的花費(fèi)是相同的，但是在不同機(jī)器人工廠購買機(jī)器人的花費(fèi)不一定相同。
購買機(jī)器人花費(fèi)的金幣，在游戲結(jié)束時(shí)再從小新收集的金幣中扣除，所以在游戲過程中小新不用擔(dān)心因金幣不足，無法購買機(jī)器人而導(dǎo)致游戲無法進(jìn)行。也因?yàn)槿绱耍螒蚪Y(jié)束后，收集的金幣數(shù)量可能為負(fù)。
現(xiàn)在已知每段馬路上每個(gè)單位時(shí)間內(nèi)出現(xiàn)的金幣數(shù)量和在每個(gè)機(jī)器人工廠購買機(jī)器人需要的花費(fèi)，請你告訴小新，經(jīng)過 m 個(gè)單位時(shí)間后，扣除購買機(jī)器人的花費(fèi)，小新最多能收集到多少金幣。
【輸入輸出格式】
【輸入格式】
第一行 3 個(gè)正整數(shù)，n，m，p，意義如題目所述。
接下來的n 行，每行有m個(gè)正整數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，其中第 i 行描
述了 i 號馬路上每個(gè)單位時(shí)間內(nèi)出現(xiàn)的金幣數(shù)量（1≤金幣數(shù)量≤100），即第i行的第 j（1≤j≤m）個(gè)數(shù)表示第 j 個(gè)單位時(shí)間內(nèi)i號馬路上出現(xiàn)的金幣數(shù)量。
最后一行，有 n 個(gè)整數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，其中第 i 個(gè)數(shù)表示在 i 號機(jī)器人工廠購買機(jī)器人需要花費(fèi)的金幣數(shù)量（1≤金幣數(shù)量≤100）。
【輸出格式】
共一行，包含 1 個(gè)整數(shù)，表示在 m 個(gè)單位時(shí)間內(nèi)，扣除購買機(jī)器人花費(fèi)的金幣之后，小新最多能收集到多少金幣。
【思路】
用一維數(shù)組f儲存第i秒能獲得的最大錢數(shù)
因?yàn)樽疃嗤瑫r(shí)存在1個(gè)機(jī)器人
第i秒時(shí)第j個(gè)機(jī)器人走k次(1<=k<=p)
f[i]=max(f[i]，f[i-k]-payst]+sum)
這里是從當(dāng)前點(diǎn)倒推
st是上一個(gè)點(diǎn)
st=0st=n
sum要一遍遍加上錢k秒st路上的金幣數(shù)
每次減去st條道路（即st個(gè)工廠機(jī)器人）的價(jià)格
如果i-k<0
直接退出k循環(huán)，時(shí)間不為負(fù)
【代碼】
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n，m，p，b[1001]，a[1001][1001]，f[1001];
int main()
{
scanf(“%d%d%d“，&n，&m，&p);
memset(f，-1000000，sizeof(f)); f[0]=0;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf(“%d“，&a[i][j]);
for(int i=1;i<=n;i++) scanf(“%d“，&b[i]);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
int t=j-1;
if(!t) t=n;
int ss=a[t][i];
for(int k=1;k<=p;k++)
{
if(i-k<0) break;
f[i]=max(f[i]，f[i-k]+ss-b[t]);
t--;
if(!t) t=n;
ss+=a[t][i-k];
}
}
printf(“%d“，f[m]);
return 0;
}
【數(shù)據(jù)范圍】
對于 40%的數(shù)據(jù)，2≤n≤40，1≤m≤40。
對于 90%的數(shù)據(jù)，2≤n≤200，1≤m≤200。
對于 100%的數(shù)據(jù)，2≤n≤1000，1≤m≤1000，1≤p≤m。
【做法說明】
題目呢，比較長，信息比較多，注意不要看錯(cuò)題。但是呢還是比較輕易可以看出這是dp題的類型。
dp[i][j]表示時(shí)間i在j點(diǎn)的最大收益，pre[j]表示j點(diǎn)的上一個(gè)，mx[i]表示在時(shí)間i所有位置的最大收益（因?yàn)橘I機(jī)器人是任意位置可買，轉(zhuǎn)移時(shí)直接用即可），g[i][j]表示狀態(tài)(i，j)取最優(yōu)解時(shí)走的步數(shù)（這個(gè)明顯是越小越好啦），最后輸出max（dp[m][i]）。
王老師說：“高中駕駛學(xué)科奧賽，要更多地運(yùn)用到數(shù)學(xué)與信息學(xué)的知識，請大家有機(jī)會課外都多補(bǔ)一補(bǔ)這方面的知識。”
沈笑夫心里一陣咯噔，數(shù)學(xué)和信息學(xué)，要加油啊！
這時(shí)，坐在旁邊的一個(gè)男生對沈笑夫說：“沈笑夫，我是汽車三班的劉李陽，請多關(guān)照！”
沈笑夫側(cè)目一看，這個(gè)男生臉色白凈，頭發(fā)新潮，一臉虔誠地看著自己。
沈笑夫點(diǎn)點(diǎn)頭說：“互相關(guān)照！”
“有你這個(gè)大佬罩著，我心里有譜了，呵呵！”劉李陽笑著說。
……
下課后，沈笑夫眼前出現(xiàn)了駕駛學(xué)科奧賽系統(tǒng)顯示屏：
學(xué)科： L1，288/1000
??體能： L1，97/100
情緒： L1，89/100
任務(wù)： 0
獎(jiǎng)勵(lì)：獎(jiǎng)勵(lì)記憶膠囊一粒。請點(diǎn)擊“兌獎(jiǎng)”鍵領(lǐng)取獎(jiǎng)勵(lì)。
學(xué)科、獎(jiǎng)勵(lì)欄的背景亮著光，說明這兩項(xiàng)有了變化！其他欄目背景灰暗，說明沒有變化。
學(xué)科欄從284到288，增加了4個(gè)點(diǎn)，是這幾天學(xué)習(xí)駕駛學(xué)科知識的收獲。
獎(jiǎng)勵(lì)欄再次出現(xiàn)久違的記憶膠囊！
沈笑夫有些雞凍，輕輕點(diǎn)擊“兌獎(jiǎng)”鍵，屏幕里立馬滾出一粒藍(lán)色的記憶膠囊！
好！
記憶膠囊在手，復(fù)雜的信息學(xué)，也就容易了！
麻煩的數(shù)學(xué)，也不會那么麻煩了！
沈笑夫嘴角露出了開森的笑容！
【精彩東方文學(xué) www.nuodawy.com】 提供武動乾坤等作品手打文字版最新章節(jié)首發(fā)，txt電子書格式免費(fèi)下載歡迎注冊收藏。