有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来，如何才能让这个和尽量大。
等等，这个题目好像有点熟悉？这不就是上课讲的数字三角形问题吗？但这一回，伟大领袖 zxh 还想要你给他指出一条这样的路线，即用一个长度为 的字符串描述每一步分别应当向左下方走（L）还是右下方走（R）。如果有多种方案，任意输出一种即可。
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，任意输出一种即可。
，三角形中的数是介于 的正整数。
提示：如何输出方案？可以在每个位置转移 dp 时顺便记录一个 int 数组 fa 表示它是由左上角转移而来还是右上角转移而来的，然后找到最后一行的最优解的位置，依据数组 fa 倒推回到起点。例如可以这样记录: （状态转移请自行补全代码）
int
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 是最后一行最优解的位置，那么可以类似这样倒推来记录方案：
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()); // 由于是倒推的，所以要翻转字符串得到正着走的路线