学步园

题目大意：给你一个由格子组成的沙漏，问你从头往下的路径中，和为s的总共有多少条，并输出，如果条数大于0，那么先选择起始位置小的，如果起始位置相同，再判断后面的L、R组成的字符串，输出字典序最小的起始位置和L、R字符串。

思路：从底下直接一遍DP上来，中间分成两段，状态转移方程稍微有点不一样，设d[ i ][ j ][ k ] 表示从最后一样往上到i行j列得到值为k的数量，那么对于下面半段：d[ i ][ j ][ k ] = d[ i +1 ][ j ][ k - val ] + d[ i + 1 ][ j + 1 ][k - val]，val为i行j列本身的值，上面半段：d[ i ][ j ][ k ] = d[ i + 1][ j - 1 ][ k -val ] + d[ i + 1][ j ][ k - val]
。转移状态的时候顺便记录路径，因为是字典序最小，那么能从左儿子转移就从左儿子转移，不行再是右儿子。全搞完以后，下面就简单了，扫一遍第一行，把和为s的全加起来，并记录最小的起始位置，然后路径的话就只要一遍dfs找下去了好了。

以下是我个人对这道题的反思：这题我反正是做了很久，+1，-1什么的真心搞得头疼，先开始数组开小了，编译器直接把内存重叠了，因为值不对，找了好久才找出这个问题，现在的编译器真是越来越强大了。。我的一开始想法是把它分成两个部分，都是从个数大的到小的进行DP，然后枚举s的分在两个部分的数值，在乘起来算总个数。这样个数是算出来了，可是路径就真的搞起来太麻烦了，因为我的路径不是从上到下，对于每个三角形都是从底向上的，还要比较字符串什么的。。唉，就去看了下网上别人怎么写的，看到他是一遍直接从下往上的，然后这样找路径就简单了。。。
看来之后，马上自己就上手敲了，敲完之后，一交WA了，检查来检查去，也试了很多组数据，没检查出有什么问题，后来哪里改了改，AC了，原来是最后dfs找路径那里，我本来的终止条件是s == 0，后来改为了 i > 2*n-2，他的数值范围是0~9，可能会是0啊，无语。。 = =

不想说什么了，代码如下：

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long lld;

const int MAXN = 22 ;

int n;

int map[MAXN<<1][MAXN];

lld d[MAXN<<1][MAXN][555];
int path[MAXN<<1][MAXN][555];

void dfs(int i,int j,int s)
{
    if(i > 2*n-2 ) return ;
    if(path[i][j][s]==0)
    {
        if(i < 2*n-2) printf("L");
        if(i<n-1)
            dfs(i+1,j-1,s-map[i][j]);
        else dfs(i+1,j,s-map[i][j]);
    }
    else
    {
        if(i < 2*n-2) printf("R");
        if(i<n-1)
            dfs(i+1,j,s-map[i][j]);
        else dfs(i+1,j+1,s-map[i][j]);
    }
}

int main()
{
    int s;
    while(~scanf("%d%d",&n,&s))
    {
        if(n==0&&s==0) break;

        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<n-i;j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        for(int i = n;i<=2*n-2;i++)
            for(int j = 0;j<=i-n+1;j++)
            {
                scanf("%d",&map[i][j]);
            }

        memset(d,0,sizeof(d));

        for(int i= 0;i<n;i++)
        {
            d[2*n-2][i][map[2*n-2][i]] = 1;
        }

        for(int i = 2*n-3;i>=n-1;i--)
        {
            for(int j = 0;j<=i-n+1;j++)
            {
                for(int k = map[i][j];k<=s;k++)
                {
                    d[i][j][k] = d[i+1][j][k-map[i][j]] + d[i+1][j+1][k-map[i][j]];
                    if(d[i+1][j][k-map[i][j]])
                    {
                        path[i][j][k] = 0;
                    }
                    else path[i][j][k] = 1;
                }
            }
        }

        for(int i =n-2;i>=0;i--)
            for(int j = 0;j<n-i;j++)
            {
                for(int k = map[i][j];k<=s;k++)
                {
                    d[i][j][k] = d[i+1][j][k-map[i][j]] ;
                    if(j>0) d[i][j][k] += d[i+1][j-1][k-map[i][j]];

                    if(j>0&&d[i+1][j-1][k-map[i][j]])
                        path[i][j][k] = 0;
                    else path[i][j][k] = 1;
                }
            }

        int ans_pos=0;
        lld tot = 0;
        for(int i =n-1;i>=0;i--)
            if(d[0][i][s])
            {
                ans_pos = i;
                tot += d[0][i][s];
            }
        printf("%lld\n",tot);
        if(tot)
        {
            printf("%d ",ans_pos);
            dfs(0,ans_pos,s);
        }
        puts("");
    }
    return 0;
}