#1160. zxh的业界良心

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: YangDavid

题目描述

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

等等,这个题目好像有点熟悉?这不就是上课讲的数字三角形问题吗?但这一回,伟大领袖 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,任意输出一种即可。

数据范围与提示

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

提示:如何输出方案?可以在每个位置转移 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 代表右上角转移而来
    }

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

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