题目传送门
Description
给出一个 \(3\times n\) 的带权矩阵，选出一个 \((1,1)\to (3,n)\) 的路径使得路径上点权之和最大。
\(n\le 10^5\)
Solution
感觉挺妙的一个题，不知道为什么在 CF 上评分只有 2300，或许是因为外国人科技树比较偏。/kk
可以想到的是，任何左走的情况一定都可以变为每次只往左边走一格的情况，那么我们就可以直接 dp 了。
Code
题目传送门
Description
给出一个 \(3\times n\) 的带权矩阵，选出一个 \((1,1)\to (3,n)\) 的路径使得路径上点权之和最大。
\(n\le 10^5\)
Solution
感觉挺妙的一个题，不知道为什么在 CF 上评分只有 2300，或许是因为外国人科技树比较偏。/kk
可以想到的是，任何左走的情况一定都可以变为每次只往左边走一格的情况，那么我们就可以直接 dp 了。
Code
![POJ 1284 Primitive Roots (欧拉函数&原根定理)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)