vue做移动端网站与pc端有什么区别,aspcms网站后台登陆界面模版,建设网站人员,陕西交通建设网站题目描述
小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路#xff0c;马路上有 nn 个机器人工厂#xff0c;两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点#xff0c;按顺时针顺序依次将这 nn 个机器人工厂编号为 1\sim n1∼n#xff0c;因…题目描述
小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路马路上有 nn 个机器人工厂两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点按顺时针顺序依次将这 nn 个机器人工厂编号为 1\sim n1∼n因为马路是环形的所以第 nn 个机器人工厂和第 11 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 nn 段马路也编号为 1\sim n1∼n并规定第 ii 段马路连接第 ii 个机器人工厂和第 i1i1 个机器人工厂1\le i\le n-11≤i≤n−1第 nn 段马路连接第 nn 个机器人工厂和第 11 个机器人工厂。
游戏过程中每个单位时间内每段马路上都会出现一些金币金币的数量会随着时间发生变化即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买机器人一旦被购买便会沿着环形马路按顺时针方向一直行走在每个单位时间内行走一次即从当前所在的机器人工厂到达相邻的下一个机器人工厂并将经过的马路上的所有金币收集给小新例如小新在 ii1\le i\le n1≤i≤n号机器人工厂购买了一个机器人这个机器人会从 ii 号机器人工厂开始顺时针在马路上行走第一次行走会经过 ii 号马路到达 i1i1 号机器人工厂如果 inin机器人会到达第 11 个机器人工厂并将 ii 号马路上的所有金币收集给小新。游戏中环形马路上不能同时存在 22 个或者 22 个以上的机器人并且每个机器人最多能够在环形马路上行走 pp 次。小新购买机器人的同时需要给这个机器人设定行走次数行走次数可以为 1~p1 p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失小新必须立刻在任意一个机器人工厂中购买一个新的机器人并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明
游戏从小新第一次购买机器人开始计时。购买机器人和设定机器人的行走次数是瞬间完成的不需要花费时间。购买机器人和机器人行走是两个独立的过程机器人行走时不能购买机器人购买完机器人并且设定机器人行走次数之后机器人才能行走。在同一个机器人工厂购买机器人的花费是相同的但是在不同机器人工厂购买机器人的花费不一定相同。购买机器人花费的金币在游戏结束时再从小新收集的金币中扣除所以在游戏过程中小新不用担心因金币不足无法购买机器人而导致游戏无法进行。也因为如此游戏结束后收集的金币数量可能为负。
现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费请你告诉小新经过 mm 个单位时间后扣除购买机器人的花费小新最多能收集到多少金币。
输入格式
第一行 33 个正整数 n,m,pn,m,p意义如题目所述。
接下来的 nn 行每行有 mm 个正整数每两个整数之间用一个空格隔开其中第 ii 行描。
述了 ii 号马路上每个单位时间内出现的金币数量1\le1≤ 金币数量 \le 100≤100即第 ii 行的第 jj1\le j\le m1≤j≤m个数表示第 jj 个单位时间内 ii 号马路上出现的金币数量。
最后一行有 nn 个整数每两个整数之间用一个空格隔开其中第 ii 个数表示在 ii 号机器人工厂购买机器人需要花费的金币数量1\le1≤ 金币数量 \le 100≤100。
输出格式
共一行包含 11 个整数表示在 mm 个单位时间内扣除购买机器人花费的金币之后小新最多能收集到多少金币。
输入数据 1
2 3 2
1 2 3
2 3 4
1 2Copy
输出数据 1
5Copy
提示
对于 40\%40% 的数据2\le n\le 402≤n≤401\le m\le 401≤m≤40。
对于 90\%90% 的数据2\le n\le 2002≤n≤2001\le m\le 2001≤m≤200。
对于 100\%100% 的数据2\le n\le 10002≤n≤10001\le m\le 10001≤m≤10001\le p\le m1≤p≤m。
NOIP 2009 普及组 第四题 代码:
#includeiostream
#includecstdio
#includecstring
#define get(i, j) (f[i] - sum[i][j] - c[j])
using namespace std;
const int N 1005;int l[N], r[N], q[N][N], pos[N][N];
int sum[N][N], val[N][N], g[N][N], c[N], f[N];int main()
{int n, m, p;scanf(%d%d%d, n, m, p);for (int i 1; i n; i)for (int j 1; j m; j)scanf(%d, val[i % n][j]);//将道路带来的收益交给点for (int i 1; i m; i)for (int j 0; j n; j)sum[i][j] sum[i - 1][(j - 1 n) % n] val[j][i];//处理对角线上的前缀和for (int i 0; i n; i){scanf(%d, c[i]);q[i][r[i]] -c[i];//初始化单调队列}memset(f, -0x3f, sizeof(f));f[0] 0;for (int i 1; i m; i){for (int j 0; j n; j){int id ((j - i) % n n) % n;while (l[id] r[id] pos[id][l[id]] p i)l[id];if (l[id] r[id])f[i] max(f[i], q[id][l[id]] sum[i][j]);}//更新答案for (int j 0; j n; j){int id ((j - i) % n n) % n;while (l[id] r[id] q[id][r[id]] get(i, j))r[id]--;q[id][r[id]] get(i, j);pos[id][r[id]] i;//记录一个位置,以判断是否合法}//更新单调队列}printf(%d, f[m]);return 0;
}
