状态表示
$f(i,j,k)$表示走到$(i,j)$,且$score\mod(K + 1) = k$的分数
属性 $Max$
$f(i,j, score\mod(K + 1)) = \max(f(i+1,j+1,k) + g_{i,j},f(i+1,j-1,k) + g_{i,j})$

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m,k;
char g[N][N];
int f[N][N][N],G[N][N][N], F[N][N][N];
int main(){
    cin>>n>>m>>k;
    for(int i = 1;i<=n;i ++)
        scanf("%s",g[i] + 1);
    for(int i = 0;i<=n;i ++)
        for(int j = 0;j<=m;j ++)
            for(int l = 0;l<=k;l ++)f[i][j][l] = -1;
    for(int i = 1;i<=m;i ++)f[n + 1][i][0] = 0;
    for(int i = n;i;i --)
        for(int j = 1;j<=m;j ++)
            for(int l = 0;l<=k;l ++){
                if(j > 1){
                    if(f[i + 1][j - 1][l] != -1){
                        int t = f[i + 1][j - 1][l] + g[i][j] - '0';
                        if(f[i][j][t % (k + 1)] == -1)
                            f[i][j][t % (k + 1)] = t,G[i][j][t % (k + 1)] = 2,F[i][j][t % (k + 1)] = l;
                        else
                            if(t > f[i][j][t % (k + 1)])
                                f[i][j][t % (k + 1)] = t,G[i][j][t % (k + 1)] = 2,F[i][j][t % (k + 1)] = l;
                        }
                }
                if(j<m)
                    if(f[i + 1][j + 1][l] != -1){
                        int t = f[i + 1][j + 1][l] + g[i][j] - '0';
                        if(f[i][j][t % (k + 1)] == -1)
                            f[i][j][t % (k + 1)] = t,G[i][j][t % (k + 1)] = 1,F[i][j][t % (k + 1)] = l;
                        else
                            if(t > f[i][j][t % (k + 1)])
                                f[i][j][t % (k + 1)] = t,G[i][j][t % (k + 1)] = 1,F[i][j][t % (k + 1)] = l;
                    }
            }
    int ans = -1;
    int tmp = 0;
    for(int i = 1;i<=m;i ++){
        ans < f[1][i][0] ? (tmp = i,ans = f[1][i][0]):0;
    }
    cout<<ans<<endl;
    if(ans == -1)return 0;

    string Ans = "";
    int tmpt = 0;
    for(int i = 1;i<=n;i ++){
        int v = F[i][tmp][tmpt];
        if(G[i][tmp][tmpt] == 1)(Ans += "L",tmp ++);
        else if(G[i][tmp][tmpt] == 2)(Ans += "R",tmp --);
        if(i == n-1)cout<<tmp<<endl;
        tmpt = v;
    }
    for(int i = Ans.size() - 2;i>=0;i--)cout<<Ans[i];
    cout<<endl;
    return 0;
}