D. Pawn
感觉这种dp套路似乎非常常见，我们可以设
f[i][j][x]表示走到(i,j)，当前的值为f[i][j][x]*k+x ,也就是我们将余数x作为放在状态中。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int mo=998244353;
const int inf=1<<30;
const int N=105;
char s[N];
int n,m,f[N][N][15],k;
int a[N][N];
void cmax(int &x,int y){
x=max(x,y);
}
void print(int i,int j,int x){
if (i==n) {
printf("%d\n",j);
return;
}
fo(z,0,k) {
if ((z+a[i][j])%k==x) {
if (f[i+1][j-1][z]+ (a[i][j]+z)/k ==f[i][j][x]) {
print(i+1,j-1,z);
printf("R");
return;
}
if (f[i+1][j+1][z]+ (a[i][j]+z)/k ==f[i][j][x]) {
print(i+1,j+1,z);
printf("L");
return;
}
}
}
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
k++;
fo(i,1,n) {
scanf("%s",s+1);
fo(j,1,m) {
a[i][j]=s[j]-'0';
}
}
fo(i,0,n+1) fo(j,0,m+1) fo(x,0,k) f[i][j][x]=-inf;
fo(i,1,m) f[n][i][a[n][i]%k]=a[n][i]/k;
fd(i,n-1,1) {
fo(j,1,m) {
fo(x,0,k-1){
cmax(f[i][j][(a[i][j]+x)%k], f[i+1][j-1][x]+(a[i][j]+x)/k);
cmax(f[i][j][(a[i][j]+x)%k], f[i+1][j+1][x]+(a[i][j]+x)/k);
}
}
}
int p;
int ans=-inf;
fo(i,1,m) {
// cmax(ans, f[1][i][0]);
if (ans<f[1][i][0]) {
ans=f[1][i][0];
p=i;
}
}
if (ans<0) {
puts("-1");
return 0;
}
else printf("%d\n",ans*k);
print(1,p,0);
return 0;
}