UVA 10564 Paths through the Hourglass .

题目地址: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;
}