C. 简单题3

本题镜像题目 ID 是 1160 (点击数字转到题库)

有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来，如何才能让这个和尽量大。

等等，这个题目好像有点熟悉？这不就是上课讲的数字三角形问题吗？但这一回，伟大领袖 zxh 还想要你给他指出一条这样的路线，即用一个长度为 的字符串描述每一步分别应当向左下方走（L）还是右下方走（R）。如果有多种方案，任意输出一种即可。

第一个行一个正整数 ,表示行的数目。

后面每行为这个数字三角形这一行包含的整数。

第一行一个整数，代表那个可能得到的最大的和。

第二行描述方案，输出一个长度为 的 LR 字符串。

样例输入1

5
7
3 8
8 1 1
2 7 4 4
4 5 2 6 5 

样例输出1

30
LLRL

样例解释：

        7 
      3   8 
    8   1   1  
  2   7   4   4 
4   5   2   6   5 

在上面的样例中,从 的路径产生了最大，因此输出字符串 LLRL。

样例输入2

3
1
1 1
1 1 1

样例输出2

3
LR

样例解释：在上面样例中，LL, LR, RL, RR 路径均可达到最大可能的和 3，任意输出一种即可。

，三角形中的数是介于 的正整数。