给定一个棋盘，你从最下面一行任选一个位置开始移动，每次只能向右上方或者左上方移动，求满足经过路径的权值和是 k+1k+1 （给定常数）的倍数的情况下最大权值和是多少。
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int N=110;
int n,m,M,a[N][N],f[N][N][50],p[N][N][50];
void print(int i,int j,int k){
if(i==n){
cout<<j<<endl; return ;
}
if(p[i][j][k]==1){
print(i+1,j+1,((k-a[i][j])%M+M )%M);
cout<<'L'; return ;
}
if(p[i][j][k]==2){
print(i+1,j-1,((k-a[i][j])%M+M )%M);
cout<<'R';return ;
}
}
signed main(){
int i,j,k;
cin>>n>>m>>M; ++M;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){char c;cin>>c;a[i][j]=c-'0';}
memset(f,-1,sizeof f) ;
for(i=1;i<=m;i++) f[n][i][a[n][i]%M] =a[n][i];
for(i=n-1;i>0;i--)
for(j=1;j<=m;j++)
for(k=0;k<M;k++){
// if(k>=a[i][j])
int t1=f[i+1][j+1][ ((k-a[i][j])%M+M )%M],
t2=f[i+1][j-1][ ((k-a[i][j])%M+M)%M];
if(j+1<=m&&~t1&&t1+a[i][j]>=f[i][j][k])
f[i][j][k] =t1+a[i][j],p[i][j][k]= 1;
if(j-1>=1&&~t2&&t2+a[i][j]>=f[i][j][k])
f[i][j][k]=t2+a[i][j],p[i][j][k]=2 ;
}
int id =0;
for(i=1;i<=m;i++)
if(f[1][i][0]>f[1][id][0]) id=i;
if(f[1][id][0]==-1) {cout<<-1<<endl;return 0;}
cout<<f[1][id][0]<<endl;
print(1,id,0) ;
}