題目描述

小新正在玩一個(gè)簡(jiǎn)單的電腦游戲。

游戲中有一條環(huán)形馬路，馬路上有?nn個(gè)機(jī)器人工廠，兩個(gè)相鄰機(jī)器人工廠之間由一小段馬路連接。小新以某個(gè)機(jī)器人工廠為起點(diǎn)，按順時(shí)針順序依次將這?nn個(gè)機(jī)器人工廠編號(hào)為1-n1?n，因?yàn)轳R路是環(huán)形的，所以第nn?個(gè)機(jī)器人工廠和第11個(gè)機(jī)器人工廠是由一段馬路連接在一起的。小新將連接機(jī)器人工廠的這 n 段馬路也編號(hào)為?1-n1?n，并規(guī)定第ii段馬路連接第 i 個(gè)機(jī)器人工廠和第?i+1i+1?個(gè)機(jī)器人工廠（1≤i≤n-11≤i≤n?1），第?nn?段馬路連接第?nn?個(gè)機(jī)器人工廠和第11個(gè)機(jī)器人工廠。

游戲過(guò)程中，每個(gè)單位時(shí)間內(nèi)，每段馬路上都會(huì)出現(xiàn)一些金幣，金幣的數(shù)量會(huì)隨著時(shí)間發(fā)生變化，即不同單位時(shí)間內(nèi)同一段馬路上出現(xiàn)的金幣數(shù)量可能是不同的。小新需要機(jī)器人的幫助才能收集到馬路上的金幣。所需的機(jī)器人必須在機(jī)器人工廠用一些金幣來(lái)購(gòu)買(mǎi)，機(jī)器人一旦被購(gòu)買(mǎi)，便會(huì)沿著環(huán)形馬路按順時(shí)針?lè)较蛞恢毙凶?#xff0c;在每個(gè)單位時(shí)間內(nèi)行走一次，即從當(dāng)前所在的機(jī)器人工廠到達(dá)相鄰的下一個(gè)機(jī)器人工廠，并將經(jīng)過(guò)的馬路上的所有金幣收集給小新，例如，小新在ii（1≤i≤n1≤i≤n）號(hào)機(jī)器人工廠購(gòu)買(mǎi)了一個(gè)機(jī)器人，這個(gè)機(jī)器人會(huì)從?ii?號(hào)機(jī)器人工廠開(kāi)始，順時(shí)針在馬路上行走，第一次行走會(huì)經(jīng)過(guò)ii號(hào)馬路，到達(dá)?i+1i+1號(hào)機(jī)器人工廠（如果?i=ni=n，機(jī)器人會(huì)到達(dá)第11?個(gè)機(jī)器人工廠），并將ii?號(hào)馬路上的所有金幣收集給小新。 游戲中，環(huán)形馬路上不能同時(shí)存在22個(gè)或者?22個(gè)以上的機(jī)器人，并且每個(gè)機(jī)器人最多能夠在環(huán)形馬路上行走pp次。小新購(gòu)買(mǎi)機(jī)器人的同時(shí)，需要給這個(gè)機(jī)器人設(shè)定行走次數(shù)，行走次數(shù)可以為?1~p1?p?之間的任意整數(shù)。當(dāng)馬路上的機(jī)器人行走完規(guī)定的次數(shù)之后會(huì)自動(dòng)消失，小新必須立刻在任意一個(gè)機(jī)器人工廠中購(gòu)買(mǎi)一個(gè)新的機(jī)器人，并給新的機(jī)器人設(shè)定新的行走次數(shù)。

以下是游戲的一些補(bǔ)充說(shuō)明：

游戲從小新第一次購(gòu)買(mǎi)機(jī)器人開(kāi)始計(jì)時(shí)。

購(gòu)買(mǎi)機(jī)器人和設(shè)定機(jī)器人的行走次數(shù)是瞬間完成的，不需要花費(fèi)時(shí)間。

購(gòu)買(mǎi)機(jī)器人和機(jī)器人行走是兩個(gè)獨(dú)立的過(guò)程，機(jī)器人行走時(shí)不能購(gòu)買(mǎi)機(jī)器人，購(gòu)買(mǎi)完機(jī)器人并且設(shè)定機(jī)器人行走次數(shù)之后機(jī)器人才能行走。

在同一個(gè)機(jī)器人工廠購(gòu)買(mǎi)機(jī)器人的花費(fèi)是相同的，但是在不同機(jī)器人工廠購(gòu)買(mǎi)機(jī)器人的花費(fèi)不一定相同。

購(gòu)買(mǎi)機(jī)器人花費(fèi)的金幣，在游戲結(jié)束時(shí)再?gòu)男⌒率占慕饚胖锌鄢?#xff0c;所以在游戲過(guò)程中小新不用擔(dān)心因金幣不足，無(wú)法購(gòu)買(mǎi)機(jī)器人而導(dǎo)致游戲無(wú)法進(jìn)行。也因?yàn)槿绱?#xff0c;游戲結(jié)束后，收集的金幣數(shù)量可能為負(fù)。

現(xiàn)在已知每段馬路上每個(gè)單位時(shí)間內(nèi)出現(xiàn)的金幣數(shù)量和在每個(gè)機(jī)器人工廠購(gòu)買(mǎi)機(jī)器人需要的花費(fèi)，請(qǐng)你告訴小新，經(jīng)過(guò)?mm?個(gè)單位時(shí)間后，扣除購(gòu)買(mǎi)機(jī)器人的花費(fèi)，小新最多能收集到多少金幣。

輸入格式：

?

第一行?33?個(gè)正整數(shù)n,m,pn,m,p，意義如題目所述。

接下來(lái)的nn行，每行有?mm?個(gè)正整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，其中第 i 行描

述了?ii?號(hào)馬路上每個(gè)單位時(shí)間內(nèi)出現(xiàn)的金幣數(shù)量（1≤1≤金幣數(shù)量≤100≤100），即第?ii行的第?jj（1≤j≤m1≤j≤m）個(gè)數(shù)表示第?jj?個(gè)單位時(shí)間內(nèi) i 號(hào)馬路上出現(xiàn)的金幣數(shù)量。

最后一行，有?nn?個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，其中第ii?個(gè)數(shù)表示在ii號(hào)機(jī)器人工廠購(gòu)買(mǎi)機(jī)器人需要花費(fèi)的金幣數(shù)量（1≤1≤金幣數(shù)量≤100≤100）。

?

輸出格式：

?

共一行，包含11個(gè)整數(shù)，表示在mm?個(gè)單位時(shí)間內(nèi)，扣除購(gòu)買(mǎi)機(jī)器人

花費(fèi)的金幣之后，小新最多能收集到多少金幣。

---

emmmmm， 一個(gè)超級(jí)長(zhǎng)的題面~~~

首先想到一個(gè)(n * m * p)的暴力， 用f[i]數(shù)組表示第i時(shí)所能收集的最大金幣數(shù)， 最外層循環(huán)m的時(shí)間點(diǎn)， 中間是1 - n， 即每一個(gè)起點(diǎn)， 最后循環(huán)0 - p - 1，比較最大值； 嗯，時(shí)間大概為1e9 ，提交， 哎？ A掉了，數(shù)據(jù)過(guò)水，啦啦啦~~

#include <bits/stdc++.h>using namespace std;typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 5e5 + 100; const int MAXM = 3e3 + 10;template < typename T > inline void read(T &x) {x = 0; T ff = 1, ch = getchar();while(!isdigit(ch)) {if(ch == '-') ff = -1;ch = getchar();}while(isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}x *= ff; }template < typename T > inline void write(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0'); }int n, m, p, f[MAXN], cost[MAXN], a[MAXM][MAXM];int main() {read(n); read(m); read(p);for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) read(a[i][j]);for(int i = 1; i <= n; ++i) read(cost[i]);memset(f, -0x3f, sizeof(f));f[0] = 0;for(int i = 1; i <= m; ++i) {for(int j = 1; j <= n; ++j) {int ans = -cost[j] + f[i - 1];for(int k = 0; k < p && i + k <= m; ++k) {int q = j + k;if(q > n) q %= n;ans += a[q][i + k];f[i + k] = max(ans, f[i + k]);}}}write(f[m]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/AK-ls/p/10843862.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1070 道路游戏（noip 2009 普及组 第四题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。