uva 10564 DP+打印路径

#include<cstdio>
#include<cstring>
using namespace std;
int G[100][100];
long long int dp[56][36][560];
int main()
{
	int n,s; 
	while(~scanf("%d%d",&n,&s)&&(n+s))
	{
		for(int i=1;i<2*n;i++)
		{
		     if(i<=n)
			 for(int j=1;j<=n-i+1;j++)
			 scanf("%d",&G[i][j]);
			 else
			 for(int j=1;j<=i-n+1;j++)
			 scanf("%d",&G[i][j]);	
		}	
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
		dp[2*n-1][i][G[2*n-1][i]]=1;
		
		for(int i=2*n-2;i>=n;i--)
		for(int j=1;j<=i-n+1;j++)
		for(int k=G[i][j];k<=s;k++)
		dp[i][j][k]=dp[i+1][j][k-G[i][j]]+dp[i+1][j+1][k-G[i][j]];
		
		for(int i=n-1;i>=1;i--)
		for(int j=1;j<=n-i+1;j++)
		for(int k=G[i][j];k<=s;k++)
		dp[i][j][k]=dp[i+1][j-1][k-G[i][j]]+dp[i+1][j][k-G[i][j]];
		
		long long res=0,t=-1;
		for(int i=n;i>=1;i--)
		{
		    if(dp[1][i][s])
		    {
			    res+=dp[1][i][s];
			    t=i;
			}
		}

		if(!res)
		printf("0\n");
		else
		{
			printf("%lld\n",res);
			printf("%d ",t-1);
			for(int i=1;i<n;i++)
			{
				s-=G[i][t];
				if(dp[i+1][t-1][s])
				{
				    printf("L");
				    t--;
				}
				else
				printf("R");
			}
			for(int i=n;i<2*n-1;i++)
			{
				s-=G[i][t];
				if(dp[i+1][t][s])
	            printf("L");
	            else
	            {
	            	printf("R");
	            	t++;
				}
			}
		}
		 printf("\n");   
		 
	}
}