这题的意思就是给出一个沙漏，第一行的两个数字ｎ ， ｓ ；ｎ就是沙漏的大小，最上面一行元素的个数，ｓ就是目标权值．
要求问从第一行到最后一行所有路径中权值为ｓ的路劲有几条．
然后输出字典序最小那条路是从第一行哪一个位置开始的（第一个是位置０），并输出这条路．
如果没有路径,输出一个空行.
首先，我们记（ｉ，ｊ）这个点权值为ｎｕｍ［ｉ］［ｊ］ ，比如我们要知道从（ｉ，ｊ）这个位置到最后的权值为ｓ的路径有多少条
那么我们要知道从（ｉ ＋ １ ， ｊ） 这个位置到最后权值为ｓ － ｎｕｍ［ｉ］［ｊ］的路径条数．
再加上从（ｉ＋ 1 , j - 1）这个位置到最后权值为ｓ － ｎｕｍ［ｉ］［ｊ］的路径条数．
那么我们设f[i][j][s] 代表 从位置(i , j)到达最后,权值为s的路径有几条.
而且容易得到状态转移方程
f[i][j][s] = dp(i + 1 , j , s - num[i][j]) + dp(i + 1 , j - 1 , s -num[i][j]);但是有一点需要特别注意,在沙漏上半部,j 往下是 j - 1 和 j
但是在沙漏下半部,j往下 是 j 和 j ＋1; 所以需要判断 i < n,来决定用哪一个.
然后是要打印路径,因为要字典序最小,从左往右找到第一个可行的路径递归打印出来.
打印时只要判断往左走是否可达,可达就往左,否则往右.(保证最小)
打印时也要注意是在上半边,还是下半边:
AC代码:
#include<stdio.h>
#include<string.h>
#define ll long long
const int N = 50;
int num[N][N];
int l[N][N];
int r[N][N];
ll f[N][N][N * 10];
int n,s,high;
ll res;
ll dp(int i , int j ,int s) {
if(f[i][j][s] != -1)
return f[i][j][s];
if(num[i][j] == -1 || s < 0 )
return 0;
if(i == 2 * n - 1) {
if(s == num[i][j])
f[i][j][s] = 1;
else
f[i][j][s] = 0;
}
else {
if(i < n)
f[i][j][s] = dp(i + 1 , j , s - num[i][j]) + dp(i + 1 , j - 1 , s -num[i][j]);
else
f[i][j][s] = dp(i + 1 , j , s - num[i][j]) + dp(i + 1 , j + 1 , s -num[i][j]);
}
return f[i][j][s];
}
void print(int i , int j ,int s) {
if(i == 2 * n -1) {
printf("\n");
return ;
}
if(i < n) {
if(dp(i + 1 , j - 1, s - num[i][j]) > 0) {
printf("L");
print(i + 1 , j - 1 ,s - num[i][j]);
}
else {
printf("R");
print(i + 1 , j ,s - num[i][j]);
}
}
else {
if(dp(i + 1 , j, s - num[i][j]) > 0) {
printf("L");
print(i + 1 , j ,s - num[i][j]);
}
else {
printf("R");
print(i + 1 , j + 1 ,s - num[i][j]);
}
}
}
int main () {
while(scanf("%d%d",&n,&s) && n + s) {
memset(num, -1, sizeof(num));
memset(f, -1 , sizeof(f));
for(int i = 1; i < n; i++) {
for(int j = 1; j <= (n-i+1); j++) {
scanf("%d", &num[i][j]);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++) {
scanf("%d", &num[i+n-1][j]);
}
}
res = 0 ;
for (int i = 1 ; i <= n ; i++) {
res += dp(1 , i , s);
}
printf("%lld\n",res);
if(res == 0)
printf("\n");
else {
for (int i = 1 ; ; i++) {
if(f[1][i][s] != 0) {
printf("%d ",i - 1);
print(1 , i , s);
break;
}
}
}
}
}