题目传送门
/*
01背包(类):dp[i][j][k] 表示从(i, j)出发的和为k的方案数,那么cnt = sum (dp[1][i][s])
状态转移方程:dp[i][j][k] = dp[i+1][j][k-c] + dp[i+1][j+1][k-c];(下半部分) 上半部分类似
因为要输出字典序最小的,打印路径时先考虑L
*/
/************************************************
* Author :Running_Time
* Created Time :2015-8-9 15:45:11
* File Name :UVA_10564.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = ;
const int MAXS = 5e2 + ;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + ;
int a[MAXN*][MAXN];
ll dp[MAXN*][MAXN][MAXS];
int n, s;
void print(int x, int y, int sum) {
if (x >= * n - ) return ;
int v = a[x][y];
if (x < n) {
if (y > && dp[x+][y-][sum-v]) {
printf ("L"); print (x+, y-, sum - v);
}
else {
printf ("R"); print (x+, y, sum - v);
}
}
else {
if (dp[x+][y][sum-v]) {
printf ("L"); print (x+, y, sum - v);
}
else {
printf ("R"); print (x+, y+, sum - v);
}
}
}
int main(void) { //UVA 10564 Paths through the Hourglass
while (scanf ("%d%d", &n, &s) == ) {
if (!n && !s) break;
for (int i=; i<=n; ++i) {
for (int j=; j<=n-i+; ++j) scanf ("%d", &a[i][j]);
}
for (int i=n+; i<=*n-; ++i) {
for (int j=; j<=i-n+; ++j) scanf ("%d", &a[i][j]);
}
memset (dp, , sizeof (dp));
for (int i=; i<=n; ++i) {
int c = a[*n-][i];
dp[*n-][i][c] = ;
}
for (int i=*n-; i>=n; --i) {
for (int j=; j<=i-n+; ++j) {
int c = a[i][j];
for (int k=c; k<=s; ++k) {
dp[i][j][k] = dp[i+][j][k-c] + dp[i+][j+][k-c];
}
}
}
ll cnt = ;
for (int i=n-; i>=; --i) {
for (int j=; j<=n-i+; ++j) {
int c = a[i][j];
for (int k=c; k<=s; ++k) {
if (j > ) dp[i][j][k] += dp[i+][j-][k-c];
if (j < n - i + ) dp[i][j][k] += dp[i+][j][k-c];
}
if (i == ) cnt += dp[i][j][s];
}
}
printf ("%lld\n", cnt);
for (int i=; i<=n; ++i) {
if (dp[][i][s]) {
printf ("%d ", i-);
print (, i, s); break;
}
}
puts ("");
}
return ;
}