题意：

由0-9的数字组成一个形如沙漏的图形，要求从第一行开始沿左下或者右下到达最后一行，问有多少种不同的路径，使最后路径上的整数之和为给定的某个数。

分析：

简单计数dp，从最后一行开始，设dp[i][j][k]为从下往上已经走过i行，走到第j列，此时路径上的整数之和为k的路径种数。得到递归方程：

dp[i][j][k] += dp[i-1][j][k-a[i][j]] +dp[i-1][j + 1][k-a[i][j]];

最后dfs输出路径，注意多条路径时要求坐标字典序最小！

代码：

#include<iostream>

#include<stack>

#include<cstring>

using namespace std;

const int maxn =100, INF =0x3fffffff;

int a[maxn][maxn];

long long dp[maxn][maxn][550];

int n, p;

void dfs(int i, int j, int t)

{

  if(i == 2*n-1) return;

  int temp;

  if(i < n){

    if(j>1&&dp[2*n-i-1][j-1][t-a[i][j]]){

        cout<<'L';

        temp = j-1;

    }else{

        cout<<'R';

        temp = j;

    }

    dfs(i+1,temp,t-a[i][j]);

 }else {

        if(dp[2*n-i-1][j][t-a[i][j]]){

            cout<<'L';

            temp = j;

        }else{

            cout<<'R';

            temp = j + 1;

        }

         dfs(i+1,temp,t-a[i][j]);

    }

    return;

}

int main (void)

{

    while(cin>>n>>p && n||p){

    for(int i = 1; i <= n; i++)

        for (int j = 1; j <=n-i+1; j++)

            cin>>a[i][j];

    for(int i = n + 1; i < 2 * n; i++)

        for (int j = 1; j <= i - n + 1; j++)

            cin>>a[i][j];

    memset(dp,0,sizeof(dp));

    for(int i =  2 * n - 1; i >= n; i--)

        for(int j = 1; j <= i - n+1; j++)

            for(int k = a[i][j]; k <= p; k++){

                if(i==2*n-1 && k==a[i][j]) dp[1][j][k]=1;

                else  dp[2*n- i][j][k] += dp[2*n-i-1][j][k-a[i][j]] +dp[2*n-i-1][j + 1][k-a[i][j]];

            }

     for(int i = n-1; i > 0; i--){

        for(int j = 1; j <= n - i + 1; j++){

         for(int k = a[i][j]; k <= p; k++){

            if(j > 1)  dp[2*n - i][j][k] += dp[2*n-i-1][j - 1][k-a[i][j]];

            if(j < n-i+1)  dp[2*n- i][j][k] += dp[2*n-i-1][j][k-a[i][j]];

         }

        }

     }

    long long total = 0;

    int s;

    for(int i = n; i >= 1; i--){

        if(dp[2*n-1][i][p]>0){

                total += dp[2*n-1][i][p];

                s = i;

            }

        }

    if(total == 0) cout<<0<<endl<<endl;

    else{

        cout<<total<<endl;

        cout<<s-1<<' ';

        dfs(1,s,p);

        cout<<endl;

    }

}

    return 0;

}

• 仔细审题！！！读题上太浮躁，不止一次坑在题意上了。
• 调试时间较久，思路捋顺，写代码的时候尽量避免一些细节错误。