从下往上DP，d(i, j, k)表示第(i, j)个格子走到底和为k的路径条数。
至于字典序最小，DP的时候记录一下路径就好。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int n, sum; 7 int a[50][25]; 8 long long d[50][50][550]; 9 int p[50][50][550][2]; 10 11 int main() 12 { 13 while(scanf("%d%d", &n, &sum) == 2 && n) 14 { 15 memset(d, 0, sizeof(d)); 16 memset(p, 0, sizeof(p)); 17 for(int i = 1; i <= n; i++) 18 for(int j = 1; j <= n - i + 1; j++) scanf("%d", &a[i][j]); 19 for(int i = n + 1; i < n * 2; i++) 20 for(int j = 1; j <= i - n + 1; j++) scanf("%d", &a[i][j]); 21 22 for(int i = 1; i <= n; i++) 23 { 24 int t = a[n*2-1][i]; 25 d[n*2-1][i][t] = 1; 26 } 27 28 for(int i = n*2-2; i >= n; i--) 29 for(int j = 1; j <= i - n + 1; j++) 30 for(int k = a[i][j]; k <= sum; k++) 31 { 32 int t = k - a[i][j]; 33 if(d[i+1][j][t]) { d[i][j][k] += d[i+1][j][t]; p[i][j][k][0] = 1; } 34 if(d[i+1][j+1][t]) { d[i][j][k] += d[i+1][j+1][t]; p[i][j][k][1] = 1; } 35 } 36 37 for(int i = n - 1; i >= 1; i--) 38 for(int j = 1; j <= n - i + 1; j++) 39 for(int k = a[i][j]; k <= sum; k++) 40 { 41 int t = k - a[i][j]; 42 if(d[i+1][j-1][t]) { d[i][j][k] += d[i+1][j-1][t]; p[i][j][k][0] = 1; } 43 if(d[i+1][j][t]) { d[i][j][k] += d[i+1][j][t]; p[i][j][k][1] = 1; } 44 } 45 46 long long ans = 0; 47 for(int i = 1; i <= n; i++) ans += d[1][i][sum]; 48 printf("%lld ", ans); 49 if(!ans) { puts(""); continue; } 50 51 int j, now = sum; 52 for(int i = 1; i <= n; i++) if(d[1][i][sum]) { j = i; break; } 53 printf("%d ", j - 1); 54 55 for(int i = 1; i < n * 2 - 1; i++) 56 { 57 if(p[i][j][now][0]) 58 { 59 printf("L"); 60 now -= a[i][j]; 61 if(i < n) j--; 62 } 63 else 64 { 65 printf("R"); 66 now -= a[i][j]; 67 if(i >= n) j++; 68 } 69 } 70 puts(""); 71 } 72 73 return 0; 74 }
还有一件事想抽自己两巴掌，就是一直困惑我的谜之AC，谜之WA，是因为没关freopen，WTF！