【题解】【DP 计数与路径记录】Paths through the Hourglass(UVa10564) —— By boshi

题目大意：给定一个 (N*2-1) 层的如图的沙漏：

每一个方块只能走到下面一层相邻的方块中，同时使答案加上这个方块的分数。
题目给定这样的沙漏，和一个非负整数 S ，求：

1. 从第一层到最后一层的路径中，有几条路径上数字和为 S

2. 这些路径中出发点编号最小的（从零开始编号）路径用 “L”、“R” 表示，字典序最小的一条是什么（不存在路径输出换行）

分析:

思路 1：看到这道题，我们的第一反应肯定是：这是裸的 DP 嘛。好吧，的确是裸的 DP。于是： f[i][j][k] 表示取到第 i 行第 j 个格子时和为 k 的路径总数。pre[i][j][k] 表示 f[i][j][k] 同时，上一层取了第几个数。O(n²*S)

f[i][j][k]=f[i-1][j 上左][k-num[i][j]]+f[i-1][j 上右][k-num[i][j]];

同时更新 pre[i][j][k];（尽量选取右上的数，这样保证路径字典序最小）

问题是，继续思考发现，这样保存的路径一定是最优的吗？这样最终求出的路径的起点就不确定了。于是再用一个 start[i][j][k] 表示每个状态路径的起点？或许可以，但是有没有更好的解法呢？

思路 2：这样的题我们见的也不少了。比如 [HNOI2015] 菜肴制作, 正着拓扑如何也得不到正确而高效的解法，于是倒着拓扑，问题迎刃而解。这道题也可以使用类似的方法。从最下一行递推，f[][][] 的递推方式基本不变，只是尽量使路径向左下方偏，得到字典序最小的路径的同时起点可以方便的得到。递推完成后寻找第一个 f[1][j][S] 非零的格子开始输出路径即可。

正确性证明及推广: 这个算法的思路与双关键字排序的思路、分段式桶排、基数排序的思路类似（当然少不了 DP），举例来说，分段式桶排会先根据数字的后几位进行排序，再根据前几位排序，因为 后确定的优先级总是可以盖过先确定的。这样保证了局部最优解推广至全局最优接的时候不会因为下一次决策被破坏。所以本算法相当于先根据路径的字典序排序，再根据起点排序，从而得到满足题目要求的路径。

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 42
#define L 1
#define R 2
#define N 3

using namespace std;

int n,s;
int mp[MX][MX];
long long f[MX][MX][600];
int pre[MX][MX][600];
int beg[MX][MX][600];

int input()
{
    memset(mp,0,sizeof(mp));
    scanf("%d%d",&n,&s);
    if(n==0&&s==0)return 0;
    for(int i=n; i>=1; i--)for(int j=1; j<=i; j++)scanf("%d",&mp[n-i+1][j]);
    for(int i=2; i<=n; i++)for(int j=1; j<=i; j++)scanf("%d",&mp[i+n-1][j]);
    return 1;
}

void work()
{
    long long tot=0,tmp=0;
    int now,cur=s;
    memset(f,0,sizeof(f));
    memset(pre,0,sizeof(pre));
    memset(beg,0,sizeof(beg));
    memset(f,0,sizeof(f));
    for(int i=0;i<=n;i++)f[n*2-1][i][mp[n*2-1][i]]=1;
    for(int i=n*2-2;i>=n;i--)
    {
        for(int j=1;j<=i-n+1;j++)
        {
            for(int k=mp[i][j];k<=s;k++)
            {
                f[i][j][k]+=f[i+1][j][k-mp[i][j]];
                f[i][j][k]+=f[i+1][j+1][k-mp[i][j]];
                if(f[i+1][j][k-mp[i][j]])pre[i][j][k]=L;
                else if(f[i+1][j+1][k-mp[i][j]])pre[i][j][k]=R;
            }
        }
    }
    for(int i=n-1;i>=1;i--)
    {
        for(int j=1;j<=n-i+1;j++)
        {
            for(int k=mp[i][j];k<=s;k++)
            {
                f[i][j][k]+=f[i+1][j-1][k-mp[i][j]];
                f[i][j][k]+=f[i+1][j][k-mp[i][j]];
                if(f[i+1][j-1][k-mp[i][j]])pre[i][j][k]=L;
                else if(f[i+1][j][k-mp[i][j]])pre[i][j][k]=R;
            }
        }
    }

    for(int i=1;i<=n;i++)tot+=f[1][i][s];
    cout<<tot<<endl;
    if(tot==0){cout<<endl;return;}
    for(int i=1;i<=n;i++)if(f[1][i][s]){now=i;break;}

    cout<<now-1<<" ";
    for(int i=1;i<=n-1;i++)
    {
        tmp+=mp[i][now];
        cur-=mp[i][now];
        if(pre[i][now][cur]==L)
        {
            cout<<"L";
            now--;
        }
        else cout<<"R";
    }
    for(int i=n;i<=n*2-2;i++)
    {
        tmp+=mp[i][now];
        cur-=mp[i][now];
        if(pre[i][now][cur]==L)cout<<"L";
        else
        {
            cout<<"R";
            now++;
        }
    }
    cout<<endl;
}

int main()
{
    while(input())work();
    return 0;
}