原题： In the hourglass to the right a path is marked. A path always starts at the first row and ends at the last row. Each cell in the path (except the first) should be directly below to the left or right of the cell in the path in the PRevious row. The value of a path is the sum of the values in each cell in the path. A path is described with an integer representing the starting point in the first row (the leftmost cell being 0) followed by a direction string containing the letters ‘L’ and ‘R’, telling whether to go to the left or right. For instance, the path to the picture is described as ‘2 RRRLLRRRLR’. 
Given the values of each cell in an hourglass as well as an integer S, calculate the number of distinct paths with value S. If at least one path exist, you should also print the path with the lowest starting point. If several such paths exist, select the one which has the lexicographically smallest direction string. Input The input contains several cases. Each case starts with a line containing two integers N and S (2 ≤ N ≤ 20, 0 ≤ S < 500), the number of cells in the first row of the hourglass and the desired sum. Next follows 2N − 1 lines describing each row in the hourglass. Each line contains a space separated list of integers between 0 and 9 inclusive. The first of these lines will contain N integers, then N − 1, …, 2, 1, 2, …, N − 1, N. The input will terminate with N = S = 0. This case should not be processed. There will be less than 30 cases in the input. Output For each case, first output the number of distinct paths. If at least one path exist, output on the next line the description of the path mentioned above. If no path exist, output a blank line instead. Sample Input 6 41 6 7 2 3 6 8 1 8 0 7 1 2 6 5 7 3 1 0 7 6 8 8 8 6 5 3 9 5 9 5 6 4 4 1 3 2 6 9 4 3 8 2 7 3 1 2 3 5 5 26 2 8 7 2 5 3 6 0 2 1 3 4 2 5 3 7 2 2 9 3 1 0 4 4 4 8 7 2 3 0 0 Sample Output 1 2 RRRLLRRRLR 0
5 2 RLLRRRLR
中文： 来自（lucky 猫） 在左邊像沙漏的圖中有一條路徑被標示出來。在沙漏中的路徑總是從最上方開始到最下方結束。當由某列中的某個格子往下列走時只能往左或往右一格。而路徑的值就是經過格子的值的總和。
一條路徑以一個數字以及一連串的動作組成。數字代表此路徑從最上方一列的哪一個格子開始走起（最左方的格子編號為 0）。動作為 R 或 L 其中之一，代表該往右下或左下方走。以左圖中的路徑為例：該路徑為 2 RRRLLRRRLR
給你沙漏中每個格子的值，以及一個數 S，請你算出有多少條路徑的值為S。如果不只一條這樣的路徑存在，輸出最上方列起始位置最小的那條。如果還是不只一條存在，則輸出字典順序最小的那條。
Input
每組測試資料的第一列有2個整數N,S（2 <=N <= 20, 0 <= S < 500）。N代表沙漏中最上方列格子的數目，S代表要求路徑的值。接下來的 2N-1 列描述此沙漏中每一列的情形。每一列中的數字均介於 0 到 9 之間，且以一空白字元相隔。沙漏中各列的格子數分別為N, N-1, …, 2, 1, 2, …, N-1, N.
當N=S=0時代表輸入結束，測試資料的數目不會超過30。請參考Sample Input。
Output
對每組測試資料請輸出2列。 第一列為路徑的數目，第二列為所要求路徑的表示法。如果所要求路徑不存在，第二列請輸出空白列。請參考Sample Output。
#include <bits/stdc++.h>using namespace std;int n,s;long long dp[501][41][41];int hg[41][41];int main(){ ios::sync_with_stdio(false); while(cin>>n>>s,n+s) { for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) cin>>hg[i][j]; for(int i=n+1;i<2*n;i++) for(int j=1;j<=i-n+1;j++) cin>>hg[i][j]; memset(dp,0,sizeof(dp)); memset(mark,0,sizeof(mark)); for(int i=1;i<=n;i++) dp[hg[2*n-1][i]][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=hg[i][j];k<=s;k++) { dp[k][i][j]+=dp[k-hg[i][j]][i+1][j]; dp[k][i][j]+=dp[k-hg[i][j]][i+1][j+1]; } } } for(int i=n-1;i>=1;i--) { for(int j=1;j<=n-i+1;j++) { for(int k=hg[i][j];k<=s;k++) { dp[k][i][j]+=dp[k-hg[i][j]][i+1][j-1]; dp[k][i][j]+=dp[k-hg[i][j]][i+1][j]; } } } long long ans=0; int start=0; for(int i=1;i<=n;i++) { if(start==0&&dp[s][1][i]!=0) start=i; ans+=dp[s][1][i]; } cout<<ans<<endl; if(0==ans) { cout<<endl; continue; } else { cout<<start-1<<" "; for(int i=1;i<n;i++) { s-=hg[i][start]; if(dp[s][i+1][start-1]) { cout<<'L'; start--; } else cout<<'R'; } for(int i=n;i<2*n-1;i++) { s-=hg[i][start]; if(dp[s][i+1][start]) cout<<'L'; else { cout<<'R'; start++; } } cout<<endl; } } return 0;}从上往下算（没算路径）
#include <bits/stdc++.h>using namespace std;int n,s;long long dp[501][41][41];int hg[41][41];int main(){ ios::sync_with_stdio(false); while(cin>>n>>s,n+s) { for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++) cin>>hg[i][j]; for(int i=n+1;i<2*n;i++) for(int j=1;j<=i-n+1;j++) cin>>hg[i][j]; memset(dp,0,sizeof(dp)); memset(mark,0,sizeof(mark)); for(int i=1;i<=n;i++) dp[hg[1][i]][1][i]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=n-i+1;j++) { for(int k=hg[i][j];k<=s;k++) { dp[k][i][j]+=dp[k-hg[i][j]][i-1][j]; dp[k][i][j]+=dp[k-hg[i][j]][i-1][j+1]; } } } for(int i=n+1;i<2*n;i++) { for(int j=1;j<=i-n+1;j++) { for(int k=hg[i][j];k<=s;k++) { dp[k][i][j]+=dp[k-hg[i][j]][i-1][j]; dp[k][i][j]+=dp[k-hg[i][j]][i-1][j-1]; } } } long long ans=0; for(int i=1;i<=n;i++) { ans+=dp[s][2*n-1][i]; } cout<<ans<<endl; } return 0;}思路：
类似数塔问题，由于要求路径数，需要考虑每个数取得以后是否能够满足和为固定的s，所以需要记录s的值，又类似背包的问题。以倒三角威力，对于一个格，可以由左上的格子转移，也可以又右上的格子转移，所以状态转移方程为（从上往下算hg[i][j]为格子中的数）
dp[s][i][j]+=dp[s-hg[i][j]][i-1][j]+dp[s-hg[i][j]][i-1][j+1] (倒放的三角形） dp[s][i][j]+=dp[s-hg[i][j]][i-1][j]+dp[s-hg[i][j]][i-1][j-1] (正放的三角形）
但是此题不能从上往下算，因为打印路径的缘故，所以需要从底部往顶部推导。
新闻热点
疑难解答
