题目地址:Paths through the Hourglass
这题目好烦好烦好烦！！
因为要算种类数，所以，d[i][j][k]表示从下往上走到(i，j)格子含k数字 有几种方法
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
long long d[50][25][500];
int a[50][25],rest,n;
void DFS1(int i,int j,int w){if(i==n) {rest=w; return;}if(j>1&&d[i+1][j-1][w-a[i][j]]) {printf("L");DFS1(i+1,j-1,w-a[i][j]);}else if(j<=n-i&&d[i+1][j][w-a[i][j]]) {printf("R");DFS1(i+1,j,w-a[i][j]);}
}
void DFS2(int i,int j,int w){if(i==2*n-1) return;if(d[i+1][j][w-a[i][j]]) {printf("L");DFS2(i+1,j,w-a[i][j]);}else if(d[i+1][j+1][w-a[i][j]]) {printf("R");DFS2(i+1,j+1,w-a[i][j]);}
}
int main(int argc, char const *argv[])
{int S;while(scanf("%d%d",&n,&S)==2&&n+S){REP(i,1,n) REP(j,1,n-i+1) scanf("%d",&a[i][j]);REP(i,n+1,n+n-1) REP(j,1,i-n+1) scanf("%d",&a[i][j]);memset(d,0,sizeof(d));REP(i,1,n) d[2*n-1][i][a[2*n-1][i]]=1;REPD(i,2*n-2,n) REP(j,1,i-n+1) {int w=a[i][j];REP(k,w,S) {d[i][j][k]+=d[i+1][j][k-w];d[i][j][k]+=d[i+1][j+1][k-w];}}long long ans=0;REPD(i,n-1,1) REP(j,1,n-i+1) {int w=a[i][j];REP(k,w,S) {if(j>1) d[i][j][k]+=d[i+1][j-1][k-w];if(j<=n-i) d[i][j][k]+=d[i+1][j][k-w];}if(i==1) ans+=d[i][j][S];}printf("%lld\n", ans);REP(i,1,n) if(d[1][i][S]) {printf("%d ", i-1);DFS1(1,i,S); DFS2(n,1,rest);break;}printf("\n");}return 0;
}