Pawn（DP）

D. Pawn

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

On some square in the lowest row of a chessboard a stands a pawn. It has only two variants of moving: upwards and leftwards or upwards and rightwards. The pawn can choose from which square of the lowest row it can start its journey. On each square lay from 0 to 9 peas. The pawn wants to reach the uppermost row having collected as many peas as possible. As there it will have to divide the peas between itself and its k brothers, the number of peas must be divisible by k + 1. Find the maximal number of peas it will be able to collect and which moves it should make to do it.

The pawn cannot throw peas away or leave the board. When a pawn appears in some square of the board (including the first and last square of the way), it necessarily takes all the peas.

Input

The first line contains three integers n, m, k (2 ≤ n, m ≤ 100, 0 ≤ k ≤ 10) — the number of rows and columns on the chessboard, the number of the pawn's brothers. Then follow n lines containing each m numbers from 0 to 9 without spaces — the chessboard's description. Each square is described by one number — the number of peas in it. The first line corresponds to the uppermost row and the last line — to the lowest row.

Output

If it is impossible to reach the highest row having collected the number of peas divisible by k + 1, print -1.

Otherwise, the first line must contain a single number — the maximal number of peas the pawn can collect given that the number must be divisible by k + 1. The second line must contain a single number — the number of the square's column in the lowest row, from which the pawn must start its journey. The columns are numbered from the left to the right with integral numbers starting from 1. The third line must contain a line consisting of n - 1 symbols — the description of the pawn's moves. If the pawn must move upwards and leftwards, print L, if it must move upwards and rightwards, print R. If there are several solutions to that problem, print any of them.

Sample test(s)

input

3 3 1
123
456
789

output

16
2
RL

input

3 3 0
123
456
789

output

17
3
LR

input

2 2 10
98
75

output

-1

 

       题意：

       给出 N，M （2 ~ 100）代表有 N 行 M 列，和 K 代表有 K 个人，加上自己故一共有 K + 1 个人。从最后一列的任意一个纵列开始往上走，只能走两个方向，要不左上走，要不右上走。求出最大的总数，这个总数能整除（k + 1）。输出这个总数，纵列开始数，任一路径。

 

       思路：

       DP。dp [ i ] [ j ] [ k ] 代表 在第 i 行 j 列时候除以 （K + 1）余数为 k 的最大总和值。更新的同时，同时记录从哪个方向来的，并且记录是从哪个余数得来的。输出路径的时候要倒着输。

 

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[105][105][15];
char roat[105][105][15];
int last[105][105][15];
char Map[105][105];
int n, m, k;

int main() {

        scanf("%d%d%d", &n, &m, &k);

        ++k;

        for (int i = 0; i < n; ++i)
                scanf("%s", Map[i]);

        memset(dp, -1, sizeof(dp));
        memset(roat, 0, sizeof(roat));

        for (int i = 0; i < m; ++i) {
                int num = Map[n - 1][i] - '0';
                int left = num % k;
                dp[n - 1][i][left] = max(dp[n - 1][i][left], num);
        }

        for (int i = n - 2; i >= 0; --i) {
                for (int j = 0; j < m; ++j) {
                        int num = Map[i][j] - '0';

                        for (int kk = 0; kk < k; ++kk) {

                                if (j > 0 && dp[i + 1][j - 1][kk] != -1) {
                                        int ans1 = num + dp[i + 1][j - 1][kk];
                                        int left1 = ans1 % k;
                                        if (ans1 > dp[i][j][left1]) {
                                                dp[i][j][left1] = ans1;
                                                roat[i][j][left1] = 'L';
                                                last[i][j][left1] = kk;
                                        }
                                }

                                if (j < m - 1 && dp[i + 1][j + 1][kk] != -1) {
                                        int ans2 = num + dp[i + 1][j + 1][kk];
                                        int left2 = ans2 % k;
                                        if (ans2 > dp[i][j][left2]) {
                                                dp[i][j][left2] = ans2;
                                                roat[i][j][left2] = 'R';
                                                last[i][j][left2] = kk;
                                        }
                                }
                        }
                }
        }

        int Max = -1, e;
        for (int i = 0; i < m; ++i) {
                if (dp[0][i][0] > Max) {
                        Max = dp[0][i][0];
                        e = i;
                }
        }

        printf("%d\n", Max);
        if (Max != -1) {
                int ans = n - 2, left = 0;
                char fin[105];

                for (int i = 0; i < n - 1; ++i) {

                        if (roat[i][e][left] == 'L') {
                                left = last[i][e][left];
                                --e;
                                fin[ans--] = 'R';
                        } else {
                                left = last[i][e][left];
                                ++e;
                                fin[ans--] = 'L';
                        }

                }

                fin[n - 1] = '\0';
                printf("%d\n%s\n", e + 1, fin);

        }

        return 0;
}