P8488 「Wdoi-(-1)」恋弹者们的黑集市题目背景天弓千亦有言「能力卡终将大势所趋归于陈腐集市终将回归日常这是发展规律。」但不知为何和神明所说相悖卡片的价值遭到了炒作。有人在炒作卡的价值吗废话又或者说有倒爷在囤积这些卡片吗卡片市场秩序完全陷入混乱之时即便是神明也无法介入的集市就此出现。—TH18.5 恋弹者们的黑集市\quad\tag*{\small\textit{---TH18.5 恋弹者们的黑集市}}—TH18.5恋弹者们的黑集市魔理沙正在调查妖怪之山的高地来收集逸散在各地的能力卡片。就在此时她遇到了住在此处的驹草山如。在河童与天狗间游刃有余的驹草山如掌握着此地大量的资源。显而易见的她掌握着大量的能力卡片——这正是魔理沙探访的目标。「想要这些卡片吗那就让我们玩一个游戏吧」「赢了这些卡片就都归你输了你可要交出身上所有的卡片。」题目描述原始题意驹草山如将一个六面写满权值的骰子放在了棋盘上。棋盘上花花绿绿写着很多数字。第iii行第jjj列写有数字ai−1,j−1a_{i-1,j-1}ai−1,j−1​。「你能否获得这些能力卡片取决于你获得的分数。」魔理沙有两种方法移动这个骰子将骰子向下一列翻转或者向下一行翻转。值得注意的是翻转骰子后骰子每面上的数字就会随着翻滚而改变。现在魔理沙需要将骰子滚动至第nnn行第mmm列。魔理沙的分数被定义为所有时刻骰子与棋盘上的数字接触的那一面的数字乘上棋盘上该数字再累加起来的和。只有魔理沙最大化这个和她才能获取她所需要的卡片。你能帮帮魔理沙吗简要题意有一个n×mn\times mn×m大小的棋盘第iii行第jjj列写有数字ai−1,j−1a_{i-1,j-1}ai−1,j−1​。现在有一个骰子六个面按照前、后、左、右、上、下的顺序依次写有数字w0,w1,w2,w3,w4,w5w_0,w_1,w_2,w_3,w_4,w_5w0​,w1​,w2​,w3​,w4​,w5​。现在骰子摆放在(0,0)(0,0)(0,0)位置需要将它滚动至(n−1,m−1)(n-1,m-1)(n−1,m−1)。骰子只有两种方式滚动向下一行翻滚、向下一列翻滚。我们记一种方案的权值为整个过程中包括骰子在起点和终点时骰子最底面上写着的数字与此时骰子所在格子上写着的数字的乘积之和。为了方便读者阅读骰子上的数字已经隐去现在你需要最大化这个乘积之和。输入格式第一行有两个正整数n,mn, mn,m表示棋盘的大小。接下来nnn行mmm列描述棋盘内元素的值ai,ja_{i,j}ai,j​。接下来一行有六个整数分别表示w0,w1,w2,w3,w4,w5w_0,w_1,w_2,w_3,w_4,w_5w0​,w1​,w2​,w3​,w4​,w5​。输出格式输出共一行一个整数表示可以获得的最大权值。输入输出样例 #1输入 #15 5 2 8 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3 8 17 12 5 3 14 13 1 1 1 1 1 1输出 #197输入输出样例 #2输入 #22 5 2 8 15 3 10 5 19 19 3 5 1 2 3 4 5 6输出 #2194说明/提示样例解释样例 1 解释一种最优的方案为(0,0)→(0,1)→(1,1)→(1,2)→(1,3)→(2,3)→(3,3)→(3,4)→(4,4)(0,0)\to(0,1)\to(1,1)\to(1,2)\to(1,3)\to(2,3)\to(3,3)\to(3,4)\to(4,4)(0,0)→(0,1)→(1,1)→(1,2)→(1,3)→(2,3)→(3,3)→(3,4)→(4,4)。总权值为281919388171397281919388171397281919388171397。样例 2 解释一种最优的方案为(0,0)→(0,1)→(1,1)→(1,2)→(1,3)→(1,4)(0,0)\to(0,1)\to(1,1)\to(1,2)\to(1,3)\to(1,4)(0,0)→(0,1)→(1,1)→(1,2)→(1,3)→(1,4)。数据范围及约定Subtaskn,m≤特殊性质分值110−102100−303103A104103−50 \def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} \bm{n,m\le} \textbf{特殊性质} \textbf{分值} \\\hline 1 10 - 10 \\\hline 2 100 - 30 \\\hline 3 10^3 \textbf{A} 10 \\\hline 4 10^3 - 50 \\\hline \end{array}Subtask1234​n,m≤10100103103​特殊性质−−A−​分值10301050​​特殊性质A\textbf{A}A保证wi1,i0,1,2,⋯5w_i1,i0,1,2,\cdots 5wi​1,i0,1,2,⋯5。对于全部数据保证1≤n,m≤1031\le n,m\le 10^31≤n,m≤103∣ai∣≤103|a_i|\le 10^3∣ai​∣≤103∣wi∣≤103|w_i|\le 10^3∣wi​∣≤103。C实现#includebits/stdc.husingnamespacestd;constintN1010;constintdw[6][6]{{0,0,4,5,3,2},{0,0,5,4,2,3},{5,4,0,0,0,1},{4,5,0,0,1,0},{2,3,1,0,0,0},{3,2,0,1,0,0}};typedeflonglongll;intn,m,a[N][N],w[6];intf[N][N][6][6];signedmain(){memset(f,0xc0,sizeof(f));scanf(%d %d,n,m);for(inti1;in;i)for(intj1;jm;j)scanf(%d,a[i][j]);for(inti0;i6;i)scanf(%d,wi);f[1][1][0][3]a[1][1]*w[5];for(inti1;in;i)for(intj1;jm;j)for(intfr0;fr6;fr)for(intrt0;rt6;rt){if(frrt||(fr^1)rt||(i1j1))continue;f[i][j][fr][rt]max(f[i-1][j][dw[fr][rt]][rt],f[i][j-1][fr][dw[fr][rt]])w[dw[fr][rt]]*a[i][j];}intans0xc0c0c0c0;for(intfr0;fr6;fr)for(intrt0;rt6;rt)ansmax(ans,f[n][m][fr][rt]);printf(%d,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容