做题感悟：这题上来就暴力了一下，就过可想而知，想用过记忆划搜索但是就是为什么没想到增加一维呢??
解题思路：
因为到达每种状态都有许多的可以组成的值，so ~ 可以开三维的数组即：dp[ i ] [ j ] [ s ] 代表第 i 行 第 j 个 组合成 s 有多少种方法。用记忆化搜索比较好写，注意处理边界。还有一点很坑，路径条数要用 long long int 保存，因为这个错了两次。
代码：
#include<stdio.h>
#include<queue>
#include<cmath>
#include<string.h>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stdlib.h>
#define INT long long int
using namespace std ;
const int MY = 40 + 10 ;
const int MX = 500 + 10 ;
INT n,m,tot ;
INT dp[MY][MY][MX],g[MY][MY] ;
INT dy[4]={-1,0,0,1} ;
char s[5]={'L','R','L','R'} ;
INT DP(INT x,INT y,INT S) // 记忆化搜索
{
INT st=0,ed=0 ;
if(dp[x][y][S]!=-1)
return dp[x][y][S] ;
INT& ans = dp[x][y][S] ;
if(x<=m-1)
{
st=0 ;ed=2 ;
}
else
{
st=2 ; ed=4 ;
}
INT mx=0 ;
for(INT j=st ; j<ed ;j++)
{
INT sx=x+1 ;
INT sy=y+dy[j] ;
if(S>=g[sx][sy]&&g[sx][sy]!=-1)
mx+=DP(sx,sy,S-g[sx][sy]) ;
}
return ans=mx ;
}
void input() // 输入处理
{
n=m*2-1 ;
memset(g,-1,sizeof(g)) ;
memset(dp,-1,sizeof(dp)) ;
for(INT i=m ;i>=2 ;i--)
for(INT j=1 ;j<=i ;j++)
scanf("%lld",&g[m-i+1][j]) ;
for(INT i=m,j=1 ;i<=n ;i++,j++)
for(INT k=1 ;k<=j ;k++)
scanf("%lld",&g[i][k]) ;
for(INT i=1 ;i<=m ;i++)
dp[n][i][0]=1 ;
}
void print(INT x,INT y,INT S) // 递归输出
{
INT st=0,ed=0 ;
if(x<=m-1)
{
st=0 ;ed=2 ;
}
else
{
st=2 ; ed=4 ;
}
for(INT i=st ;i<ed ;i++)
{
INT sx=x+1 ;
INT sy=y+dy[i] ;
if(g[sx][sy]!=-1&&S>=g[sx][sy]&&dp[sx][sy][S-g[sx][sy]]>=1)
{
cout<<s[i] ;
print(sx,sy,S-g[sx][sy]) ;
break ;
}
}
}
int main()
{
while(scanf("%d%d",&m,&tot),m+tot)
{
input() ;
INT best=0 ;
for(INT i=1 ;i<=m ;i++)
{
if(tot>=g[1][i])
dp[1][i][tot]=DP(1,i,tot-g[1][i]) ;
if(dp[1][i][tot]>0)
best+=dp[1][i][tot] ;
}
cout<<best<<endl ;
if(best)
for(INT i=1 ;i<=m ;i++)
if(dp[1][i][tot]>=1)
{
cout<<i-1<<" " ;
print(1,i,tot-g[1][i]) ;
break ;
}
cout<<endl ;
}
return 0 ;
}