題目描述

小新正在玩一個簡單的電腦游戲。

游戲中有一條環形馬路，馬路上有?nn個機器人工廠，兩個相鄰機器人工廠之間由一小段馬路連接。小新以某個機器人工廠為起點，按順時針順序依次將這?nn個機器人工廠編號為1-n1?n，因為馬路是環形的，所以第nn?個機器人工廠和第11個機器人工廠是由一段馬路連接在一起的。小新將連接機器人工廠的這 n 段馬路也編號為?1-n1?n，并規定第ii段馬路連接第 i 個機器人工廠和第?i+1i+1?個機器人工廠（1≤i≤n-11≤i≤n?1），第?nn?段馬路連接第?nn?個機器人工廠和第11個機器人工廠。

游戲過程中，每個單位時間內，每段馬路上都會出現一些金幣，金幣的數量會隨著時間發生變化，即不同單位時間內同一段馬路上出現的金幣數量可能是不同的。小新需要機器人的幫助才能收集到馬路上的金幣。所需的機器人必須在機器人工廠用一些金幣來購買，機器人一旦被購買，便會沿著環形馬路按順時針方向一直行走，在每個單位時間內行走一次，即從當前所在的機器人工廠到達相鄰的下一個機器人工廠，并將經過的馬路上的所有金幣收集給小新，例如，小新在ii（1≤i≤n1≤i≤n）號機器人工廠購買了一個機器人，這個機器人會從?ii?號機器人工廠開始，順時針在馬路上行走，第一次行走會經過ii號馬路，到達?i+1i+1號機器人工廠（如果?i=ni=n，機器人會到達第11?個機器人工廠），并將ii?號馬路上的所有金幣收集給小新。 游戲中，環形馬路上不能同時存在22個或者?22個以上的機器人，并且每個機器人最多能夠在環形馬路上行走pp次。小新購買機器人的同時，需要給這個機器人設定行走次數，行走次數可以為?1~p1?p?之間的任意整數。當馬路上的機器人行走完規定的次數之后會自動消失，小新必須立刻在任意一個機器人工廠中購買一個新的機器人，并給新的機器人設定新的行走次數。

以下是游戲的一些補充說明：

游戲從小新第一次購買機器人開始計時。

購買機器人和設定機器人的行走次數是瞬間完成的，不需要花費時間。

購買機器人和機器人行走是兩個獨立的過程，機器人行走時不能購買機器人，購買完機器人并且設定機器人行走次數之后機器人才能行走。

在同一個機器人工廠購買機器人的花費是相同的，但是在不同機器人工廠購買機器人的花費不一定相同。

購買機器人花費的金幣，在游戲結束時再從小新收集的金幣中扣除，所以在游戲過程中小新不用擔心因金幣不足，無法購買機器人而導致游戲無法進行。也因為如此，游戲結束后，收集的金幣數量可能為負。

現在已知每段馬路上每個單位時間內出現的金幣數量和在每個機器人工廠購買機器人需要的花費，請你告訴小新，經過?mm?個單位時間后，扣除購買機器人的花費，小新最多能收集到多少金幣。

輸入格式：

?

第一行?33?個正整數n,m,pn,m,p，意義如題目所述。

接下來的nn行，每行有?mm?個正整數，每兩個整數之間用一個空格隔開，其中第 i 行描

述了?ii?號馬路上每個單位時間內出現的金幣數量（1≤1≤金幣數量≤100≤100），即第?ii行的第?jj（1≤j≤m1≤j≤m）個數表示第?jj?個單位時間內 i 號馬路上出現的金幣數量。

最后一行，有?nn?個整數，每兩個整數之間用一個空格隔開，其中第ii?個數表示在ii號機器人工廠購買機器人需要花費的金幣數量（1≤1≤金幣數量≤100≤100）。

?

輸出格式：

?

共一行，包含11個整數，表示在mm?個單位時間內，扣除購買機器人

花費的金幣之后，小新最多能收集到多少金幣。

---

emmmmm， 一個超級長的題面~~~

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

#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; }

?

轉載于:https://www.cnblogs.com/AK-ls/p/10843862.html

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。