原題： 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
中文： 來(lái)自（lucky 貓） 在左邊像沙漏的圖中有一條路徑被標(biāo)示出來(lái)。在沙漏中的路徑總是從最上方開(kāi)始到最下方結(jié)束。當(dāng)由某列中的某個(gè)格子往下列走時(shí)只能往左或往右一格。而路徑的值就是經(jīng)過(guò)格子的值的總和。
一條路徑以一個(gè)數(shù)字以及一連串的動(dòng)作組成。數(shù)字代表此路徑從最上方一列的哪一個(gè)格子開(kāi)始走起（最左方的格子編號(hào)為 0）。動(dòng)作為 R 或 L 其中之一，代表該往右下或左下方走。以左圖中的路徑為例：該路徑為 2 RRRLLRRRLR
給你沙漏中每個(gè)格子的值，以及一個(gè)數(shù) S，請(qǐng)你算出有多少條路徑的值為S。如果不只一條這樣的路徑存在，輸出最上方列起始位置最小的那條。如果還是不只一條存在，則輸出字典順序最小的那條。
Input
每組測(cè)試資料的第一列有2個(gè)整數(shù)N,S（2 <=N <= 20, 0 <= S < 500）。N代表沙漏中最上方列格子的數(shù)目，S代表要求路徑的值。接下來(lái)的 2N-1 列描述此沙漏中每一列的情形。每一列中的數(shù)字均介於 0 到 9 之間，且以一空白字元相隔。沙漏中各列的格子數(shù)分別為N, N-1, …, 2, 1, 2, …, N-1, N.
當(dāng)N=S=0時(shí)代表輸入結(jié)束，測(cè)試資料的數(shù)目不會(huì)超過(guò)30。請(qǐng)參考Sample Input。
Output
對(duì)每組測(cè)試資料請(qǐng)輸出2列。 第一列為路徑的數(shù)目，第二列為所要求路徑的表示法。如果所要求路徑不存在，第二列請(qǐng)輸出空白列。請(qǐng)參考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;}從上往下算（沒(méi)算路徑）
#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;}思路：
類似數(shù)塔問(wèn)題，由于要求路徑數(shù)，需要考慮每個(gè)數(shù)取得以后是否能夠滿足和為固定的s，所以需要記錄s的值，又類似背包的問(wèn)題。以倒三角威力，對(duì)于一個(gè)格，可以由左上的格子轉(zhuǎn)移，也可以又右上的格子轉(zhuǎn)移，所以狀態(tài)轉(zhuǎn)移方程為（從上往下算hg[i][j]為格子中的數(shù)）
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] (正放的三角形）
但是此題不能從上往下算，因?yàn)榇蛴÷窂降木壒剩孕枰獜牡撞客敳客茖?dǎo)。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
