题意：

要求从第一层走到最下面一层，只能往左下或右下走

问有多少条路径之和刚好等于S？ 如果有的话，输出字典序最小的路径。

---

f[i][j][k]从下往上到第i层第j个和为k的方案数

上下转移不一样，分开处理

没必要判断走出沙漏

打印方案倒着找下去行了，尽量往左走

 

沙茶的忘注释掉文件WA好多次

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=25,M=505,INF=1e9;typedef long long ll;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n,s,w[N<<1][N];ll f[N<<1][N][M];void dp(){    memset(f,0,sizeof(f));    for(int j=1;j<=n;j++)        f[n+n-1][j][w[n+n-1][j]]=1;        //xia    for(int i=n+n-2;i>=n;i--)        for(int j=1;j<=i-n+1;j++)            for(int k=w[i][j];k<=s;k++)                f[i][j][k]=f[i+1][j][k-w[i][j]]+f[i+1][j+1][k-w[i][j]];    //shang    for(int i=n-1;i>=1;i--)        for(int j=1;j<=n-i+1;j++)            for(int k=w[i][j];k<=s;k++)                f[i][j][k]=f[i+1][j][k-w[i][j]]+f[i+1][j-1][k-w[i][j]];    }void print(int i,int j,ll k){
    //printf("print %d %d %d\n",i,j,k);    if(i==n+n-1) return;    if(i
          
           1&&f[i+1][j-1][k-w[i][j]]){            putchar('L');            print(i+1,j-1,k-w[i][j]);        }else{            putchar('R');            print(i+1,j,k-w[i][j]);        }    }else{        if(f[i+1][j][k-w[i][j]]){            putchar('L');            print(i+1,j,k-w[i][j]);        }else{            putchar('R');            print(i+1,j+1,k-w[i][j]);        }    }}int main(){    //freopen("1.in","r",stdin);    //freopen("1.out","w",stdout);    while(scanf("%d%d",&n,&s)!=EOF&&(n||s)){        memset(w,0,sizeof(w));        for(int i=1;i<=n;i++)            for(int j=1;j<=n-i+1;j++) w[i][j]=read();        for(int i=n+1;i<=n+n-1;i++)            for(int j=1;j<=i-n+1;j++) w[i][j]=read();        dp();        int p=0;        ll sum=0;        for(int i=n;i>=1;i--) if(f[1][i][s]){p=i;sum+=f[1][i][s];}                printf("%lld\n",sum);        if(p) printf("%d ",p-1),print(1,p,s);        putchar('\n');    }}