【csp-j 2020 方格取数】题解依旧csp-j的题解题目传送门({[ ]})这题看了之后都应该觉得用DP吧这题最大的难点在于它能往上走我们来盘一下走的规则吧1不能向左走2不能出界3不能走回头路如果用传统格点 DP 设f [ i ] [ j ] f[i][j]f[i][j]表示走到( i , j ) (i, j)(i,j)的最大权值很容易推出状态转移方程f [ i ] [ j ] max ⁡ ( f [ i ] [ j − 1 ] , f [ i − 1 ][ j ] , f [ i 1 ] [ j ] ) a [ i ] [ j ] f[i][j] max(f[i][j-1], f[i-1][j], f[i1][j]) a[i][j]f[i][j]max(f[i][j−1],f[i−1][j],f[i1][j])a[i][j]但会有一个致命问题:(后效性) !求f [ i ] [ j ] f[i][j]f[i][j]需要知道它下面的f [ i 1 ] [ j ] f[i1][j]f[i1][j]求f [ i 1 ] [ j ] f[i1][j]f[i1][j]时又要用到它上面的f [ i ] [ j ] f[i][j]f[i][j]自己依赖自己程序死循环了。解题关键点在于因为不能重复经过已经走过的方格且无法向左走所以在列与列之间是单向向右的而在同一列中只能“单向一直向上”或“单向一直向下”绝不能反复折返。定义状态我们可以将 r[i][j]:从左方进入,u[i][j]:从上方进入,d[i][j]:从下方进入那么r[i][j]是从第j − 1 j-1j−1列的第i ii行走过来的。至于它在第j − 1 j-1j−1列时是怎么到的向上、向下、向右都有可能r[i][j]max(max(u[i][j-1],d[i][j-1]),r[i][j-1])a[i][j];u[i][j]是从当前列下方的( i 1 , j ) (i1, j)(i1,j)走过来的。为了不回头它的上一步绝对不能是从上面下来的只能是向右走到( i 1 , j ) (i1, j)(i1,j)或继续向上走到( i 1 , j ) (i1, j)(i1,j)u[i][j] max(u[i 1][j], r[i 1][j]) a[i][j];d[i][j]是从当前列上方的( i − 1 , j ) (i-1, j)(i−1,j)走过来的。同理为了不回头它的上一步只能是向右走到( i − 1 , j ) (i-1, j)(i−1,j)或继续向下走到( i − 1 , j ) (i-1, j)(i−1,j)。d[i][j] max(r[i - 1][j], d[i - 1][j]) a[i][j];最终答案就是max(max(u[n][m], d[n][m]), r[n][m])三个取最大值代码#includebits/stdc.h#definemaxn1005usingnamespacestd;intn,m,a[maxn][maxn];//r[i][j]:从左方进入,u[i][j]:从上方进入,d[i][j]:从下方进入longlongr[maxn][maxn],d[maxn][maxn],u[maxn][maxn];intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;for(inti1;in;i){for(intj1;jm;j){cina[i][j];r[i][j]u[i][j]d[i][j]-1e16;//数据有负数开1e16最安全}}r[1][1]u[1][1]d[1][1]a[1][1];//初始化起点(1,1)for(inti2;in;i){//初始第一列,i2因为(1,1)初始过了d[i][1]d[i-1][1]a[i][1];}for(intj2;jm;j){//开始DPfor(inti1;in;i){//向右r[i][j]max(max(u[i][j-1],d[i][j-1]),r[i][j-1])a[i][j];}for(intin-1;i1;i--){//向上u[i][j]max(u[i1][j],r[i1][j])a[i][j];}for(inti2;in;i){//向下d[i][j]max(r[i-1][j],d[i-1][j])a[i][j];}}//输出从上、下、右来的最大值coutmax(max(u[n][m],d[n][m]),r[n][m]);return0;}