#1160. zxh的业界良心

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

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

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

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

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

第二行描述方案，输出一个长度为 $n-1$ 的 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 

在上面的样例中,从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大，因此输出字符串 LLRL。

样例输入2

3
1
1 1
1 1 1

样例输出2

3
LR

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

$1\leq n\leq 1000$，三角形中的数是介于 $[1,100]$ 的正整数。

提示：如何输出方案？可以在每个位置转移 dp 时顺便记录一个 int 数组 fa 表示它是由左上角转移而来还是右上角转移而来的，然后找到最后一行的最优解的位置，依据数组 fa 倒推回到起点。例如可以这样记录: （状态转移请自行补全代码）

for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= i; ++j) {
        dp[i][j] = ; // 状态转移 请自行补全代码
        fa[i][j] = dp[i - 1][j] == max(dp[i - 1][j], dp[i - 1][j - 1]) ? 0 : -1;
        // fa 是 -1 代表左上角转移而来，fa 是 0 代表右上角转移而来
    }

倒推时，假设找到了 xp，yp 是最后一行最优解的位置，那么可以类似这样倒推来记录方案：

string plan;
while(xp > 1) { // 如果 xp==1，说明已经回到了初始位置，不需要再倒推了
    plan += fa[xp][yp] ? 'R' : 'L'; // 看看当前位置是怎样由上一层转移来的
    yp += fa[xp][yp], xp--; // 回到上一层的位置
}
reverse(plan.begin(), plan.end()); // 由于是倒推的，所以要翻转字符串得到正着走的路线