On some square in the lowest row of a chessboard a stands a pawn. It has only two variants of moving: upwards and leftwards or upwards and rightwards. The pawn can choose from which square of the lowest row it can start its journey. On each square lay from 0 to 9 peas. The pawn wants to reach the uppermost row having collected as many peas as possible. As there it will have to divide the peas between itself and its k brothers, the number of peas must be divisible by k + 1. Find the maximal number of peas it will be able to collect and which moves it should make to do it.
The pawn cannot throw peas away or leave the board. When a pawn appears in some square of the board (including the first and last square of the way), it necessarily takes all the peas.
The first line contains three integers n, m, k (2 ≤ n, m ≤ 100, 0 ≤ k ≤ 10) — the number of rows and columns on the chessboard, the number of the pawn's brothers. Then follow n lines containing each m numbers from 0 to 9 without spaces — the chessboard's description. Each square is described by one number — the number of peas in it. The first line corresponds to the uppermost row and the last line — to the lowest row.
If it is impossible to reach the highest row having collected the number of peas divisible by k + 1, print -1.
Otherwise, the first line must contain a single number — the maximal number of peas the pawn can collect given that the number must be divisible by k + 1. The second line must contain a single number — the number of the square's column in the lowest row, from which the pawn must start its journey. The columns are numbered from the left to the right with integral numbers starting from 1. The third line must contain a line consisting of n - 1 symbols — the description of the pawn's moves. If the pawn must move upwards and leftwards, print L, if it must move upwards and rightwards, print R. If there are several solutions to that problem, print any of them.
3 3 1 123 456 789
16 2 RL
3 3 0 123 456 789
17 3 LR
2 2 10 98 75
-1
题意:
给出 N,M (2 ~ 100)代表有 N 行 M 列,和 K 代表有 K 个人,加上自己故一共有 K + 1 个人。从最后一列的任意一个纵列开始往上走,只能走两个方向,要不左上走,要不右上走。求出最大的总数,这个总数能整除(k + 1)。输出这个总数,纵列开始数,任一路径。
思路:
DP。dp [ i ] [ j ] [ k ] 代表 在第 i 行 j 列时候除以 (K + 1)余数为 k 的最大总和值。更新的同时,同时记录从哪个方向来的,并且记录是从哪个余数得来的。输出路径的时候要倒着输。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int dp[105][105][15]; char roat[105][105][15]; int last[105][105][15]; char Map[105][105]; int n, m, k; int main() { scanf("%d%d%d", &n, &m, &k); ++k; for (int i = 0; i < n; ++i) scanf("%s", Map[i]); memset(dp, -1, sizeof(dp)); memset(roat, 0, sizeof(roat)); for (int i = 0; i < m; ++i) { int num = Map[n - 1][i] - '0'; int left = num % k; dp[n - 1][i][left] = max(dp[n - 1][i][left], num); } for (int i = n - 2; i >= 0; --i) { for (int j = 0; j < m; ++j) { int num = Map[i][j] - '0'; for (int kk = 0; kk < k; ++kk) { if (j > 0 && dp[i + 1][j - 1][kk] != -1) { int ans1 = num + dp[i + 1][j - 1][kk]; int left1 = ans1 % k; if (ans1 > dp[i][j][left1]) { dp[i][j][left1] = ans1; roat[i][j][left1] = 'L'; last[i][j][left1] = kk; } } if (j < m - 1 && dp[i + 1][j + 1][kk] != -1) { int ans2 = num + dp[i + 1][j + 1][kk]; int left2 = ans2 % k; if (ans2 > dp[i][j][left2]) { dp[i][j][left2] = ans2; roat[i][j][left2] = 'R'; last[i][j][left2] = kk; } } } } } int Max = -1, e; for (int i = 0; i < m; ++i) { if (dp[0][i][0] > Max) { Max = dp[0][i][0]; e = i; } } printf("%d\n", Max); if (Max != -1) { int ans = n - 2, left = 0; char fin[105]; for (int i = 0; i < n - 1; ++i) { if (roat[i][e][left] == 'L') { left = last[i][e][left]; --e; fin[ans--] = 'R'; } else { left = last[i][e][left]; ++e; fin[ans--] = 'L'; } } fin[n - 1] = '\0'; printf("%d\n%s\n", e + 1, fin); } return 0; }
相关推荐
Pawn helps you compare items and find upgrades
C, C++, C#, ObjectiveC, D, Java, Pawn and VALA 代码格式化
这是全局灵敏度分析算法PAWN的MATLAB实现。 PAWN.m 包含 PAWN 算法的 MATLAB 实现。 ishigami_homma.m 重新创建了论文 [1] 的图 4。 [1] Pianosi, F., Wagener, T., 2015. 一种基于累积分布函数的简单有效的全局...
Atom 编辑器的 Pawn 语法。 这是Atom的Pawn语言,可以从下载。 SA-MP 论坛上的主题: : Atom 上的包: :
pawn-3.2-plus:具有运行时修复和改进的Pawn脚本语言
无论您是需要快速赚钱,还是正在寻找价格优惠的优质产品,Easy Money Pawn&Jewelry都是奥克兰和旧金山湾地区的主要典当行! 告别您可能对典当行的任何误解! Easy Money Pawn&Jewelry干净,保养良好,并备有大量...
Pawn Studio是Pawn的增强型IDE,它支持多种功能,例如语法突出显示,代码解析,自动缩进,自动完成,调用提示和Doxygen解析。 它还支持HL1,HL2和GTA SA:MP的RCON,并具有FTP资源管理器。
\n}*/安装只需在vscode扩展名中搜索“ Pawn Community Tool”并安装它即可。 或者,您可以签出源代码或查看市场页面:创建tasks.json 按Ctrl + Shift + P或F1,然后键入> Initialize Pawn Build Task解释"command": ...
使用NASM测试Pawn的即时编译器。该代码基于原始的 Pawn示例。在提供了一个示例脚本。不过,您需要使用自己的Pawn 4编译器。 经过测试的编译器 基于使用《 Pawn实施者指南》 PDF的Borland编译器版本,我可以找到早在...
客户端执行命令插件。 本插件使用Pawn语言编写。 本插件用于该插件用于使安装AMXX模块的HL及其MOD服务器的管理员可以在用户的控制台运行指定命令。 内含:插件源码、AMXX1.81编译器、使用说明。
典当社区编译器什么这是Pawn 3.2.3664编译器的修改版本,具有许多错误修复和增强功能。 该项目最初由Zeex启动,但在2017年12月31日,该项目由SA:MP社区的一些成员接管。 Zeex和仍为该项目做出了贡献。 原始自述文件...
language-pawn:对atom的SA-MP Pawn语法支持
UE4学习笔记----使用C++之玩家控制Pawn(源代码)
Scripting-Pawn-SAMP-Belajar-Dasar:Belajar memahami脚本dasar Pawn SAMP
基于PAWN方法和RSA的GR4J和IHACRES降雨径流模型的不确定性和敏感性分析
典当库扩展测试版 ...所有的Pawn Library Extension版本都将使用major[.minor][.patch]版本控制方案。 对于较小的补丁(例如,错误修复,较小的改进等),补丁版本会增加。 测试版不受上述规则的约束。
这是SAMP SUNRISE CITY的OBJ大全,喜欢的可以安装至服务器使用。
升华文字的Pawn工具Sublime Text是功能极为丰富且可自定义的纯文本编辑器。 它的可定制性由Python脚本提供支持,并且有大量可用的扩展。 Sublime Text为您提供了一个惊人的工具集,旨在加快您的编写工作流程,无论是...
JunkBuster9是联机版圣安地列斯SAMP的一个反作弊脚本,现在上传源码文件,大家可以用自带的pawno编译器编译