UVA_10564

    我们可以用f[i][j][k]表示到第i行第j个格子时路径上值得和是否可以为k，为了保证记录的路径字典序最小的，我们可以将i由大向小循环。

    状态转移的思路还是很好想的，但是写起来有些蛋疼。

#include
     
       #include
      
        #define MAXD 50 #define MAXS 520 int N, S, f[MAXD][MAXD][MAXS], p[MAXD][MAXD][MAXS], num[MAXD], a[MAXD][MAXD]; long long int d[MAXD][MAXD][MAXS]; int init() {
   int i, j, k;     scanf("%d%d", &N, &S); if(!N && !S) return 0; for(i = 0; i < N; i ++) for(j = 0; j < N - i; j ++)         {
               scanf("%d", &a[i][j]);             num[i] = N - i;         } for(; i < 2 * N - 1; i ++) for(j = 0; j < i - N + 2; j ++)         {
               scanf("%d", &a[i][j]);             num[i] = i - N + 2;         } return 1; } void printpath(int k) {
   int i, j, t;     printf("%d ", k); for(i = 0, j = k, t = S; i < N - 1; i ++)     {
   if(p[i][j][t] == 0)         {
               printf("L");             t -= a[i][j --];         } else         {
               printf("R");             t -= a[i][j];         }     } for(; i < 2 * N - 2; i ++)     {
   if(p[i][j][t] == 0)         {
               printf("L");             t -= a[i][j];         } else         {
               printf("R");             t -= a[i][j ++];         }     } } void solve() {
   int i, j, k; long long int res;     memset(p, -1, sizeof(p));     memset(f, 0, sizeof(f));     memset(d, 0, sizeof(d)); for(i = 2 * N - 2, j = 0; j < num[i]; j ++)     {
           f[i][j][a[i][j]] = 1;         d[i][j][a[i][j]] = 1;     } for(i = 2 * N - 3; i >= N - 1; i --) for(j = 0; j < num[i]; j ++)         {
   for(k = 0; k <= S; k ++) if(f[i + 1][j][k])                 {
                       f[i][j][k + a[i][j]] = 1;                     d[i][j][k + a[i][j]] += d[i + 1][j][k];                     p[i][j][k + a[i][j]] = 0;                 } for(k = 0; k <= S; k ++) if(f[i + 1][j + 1][k])                 {
                       d[i][j][k + a[i][j]] += d[i + 1][j + 1][k]; if(!f[i][j][k + a[i][j]])                     {
                           f[i][j][k + a[i][j]] = 1;                         p[i][j][k + a[i][j]] = 1;                     }                 }         } for(i = N - 2; i >= 0; i --) for(j = 0; j < num[i]; j ++)         {
   if(j) for(k = 0; k <= S; k ++) if(f[i + 1][j - 1][k])                     {
                           f[i][j][k + a[i][j]] = 1;                         d[i][j][k + a[i][j]] += d[i + 1][j - 1][k];                         p[i][j][k + a[i][j]] = 0;                     } if(j < num[i + 1]) for(k = 0; k <= S; k ++) if(f[i + 1][j][k])                     {
                           d[i][j][k + a[i][j]] += d[i + 1][j][k]; if(!f[i][j][k + a[i][j]])                         {
                               f[i][j][k + a[i][j]] = 1;                             p[i][j][k + a[i][j]] = 1;                         }                     }         }     res = 0; for(i = 0; i < num[0]; i ++) if(f[0][i][S])         {
   if(!res)                 k = i;             res += d[0][i][S];         }     printf("%lld\n", res); if(res)         printpath(k);     printf("\n"); } int main() {
   while(init())         solve(); return 0; }