[UVA][dp] 10564 - Paths through the Hourglass
Problem F
Paths through the Hourglass
Input: Standard Input
Output: Standard Output
Time Limit: 2 Seconds
In the
hourglass to the right a path is marked. A path always starts at the first row
and ends at the last row. Each cell in the path (except the first) should be
directly below to the left or right of the cell in the path in the previous
row. The value of a path is the sum of the values in each cell in the path.
A path is described with an integer representing the starting point in the first row (the leftmost cell being 0) followed by a direction string containing the letters L and R, telling whether to go to the left or right. For instance, the path to the right is described as 2 RRRLLRRRLR.
Given the values of each cell in an hourglass as well as an integer S, calculate the number of distinct paths with value S. If at least one path exist, you should also print the path with the lowest starting point. If several such paths exist, select the one which has the lexicographically smallest direction string.
Input
The input contains several cases. Each case starts with a line containing two integers N and S (2≤N≤20, 0≤S<500), the number of cells in the first row of the hourglass and the desired sum. Next follows 2N-1 lines describing each row in the hourglass. Each line contains a space separated list of integers between 0 and 9 inclusive. The first of these lines will contain N integers, then N-1, ..., 2, 1, 2, ..., N-1, N.
The input will terminate with N=S=0. This case should not be processed. There will be less than 30 cases in the input.
Output
For each case, first output the number of distinct paths. If at least one path exist, output on the next line the description of the path mentioned above. If no path exist, output a blank line instead.
Sample Input Output for Sample Input
|
6 41 6 7 2 3 6 8 1 8 0 7 1 2 6 5 7 3 1 0 7 6 8 8 8 6 5 3 9 5 9 5 6 4 4 1 3 2 6 9 4 3 8 2 7 3 1 2 3 5 5 26 2 8 7 2 5 3 6 0 2 1 3 4 2 5 3 7 2 2 9 3 1 0 4 4 4 8 7 2 3 0 0 |
1 2 RRRLLRRRLR 0
5 2 RLLRRRLR
|
Problemsetter: Jimmy Mårdell, Member of Elite Problemsetters' Panel
題目是期望找到一條從最上層的任意起點到達最下層的路徑上的總和為指定數值。
並且輸出方法數(long long)有幾種，且輸出一條字典順序最小的，起點越靠近左邊越好。
圖會比較難建，由於給定的是沙漏的樣子，接著可以使用 dp 去記錄。
dp[i][j][k] 表示該點位置(i, j) 到這邊總和為 k 的方法數，藉此去推算便可得到。
#include <string.h>
int g[100][50][2][2], gt[100];
int vg[100][50][2][2];
long long dp[100][50][505];
int main() {
int n, s;
int i, j, k;
int a[100][50];
while(scanf("%d %d", &n, &s) == 2 && n) {
int m = 0;
memset(g, -1, sizeof(g));
memset(vg, -1, sizeof(vg));
for(i = n; i >= 1; i--) {
for(j = 0; j < i; j++) {
scanf("%d", &a[m][j]);
if(m) {
//L
g[m][j][0][0] = m-1,g[m][j][0][1] = j;
vg[m-1][j][1][0] = m, vg[m-1][j][1][1] = j;
//R
g[m][j][1][0] = m-1, g[m][j][1][1] = j+1;
vg[m-1][j+1][0][0] = m, vg[m-1][j+1][0][1] = j;
}
}
gt[m] = i;
m++;
}
for(i = 2; i <= n; i++) {
for(j = 0; j < i; j++)
scanf("%d", &a[m][j]);
for(j = 0; j < i; j++) {
if(j) {
g[m][j][0][0] = m-1, g[m][j][0][1] = j-1;
vg[m-1][j-1][1][0] = m, vg[m-1][j-1][1][1] = j;
}
if(j != i-1) {
g[m][j][1][0] = m-1, g[m][j][1][1] = j;
vg[m-1][j][0][0] = m, vg[m-1][j][0][1] = j;
}
}
gt[m] = i;
m++;
}
n = 2*n-1;
for(i = 0; i < n; i++)
for(j = 0; j < gt[i]; j++)
for(k = 0; k <= s; k++)
dp[i][j][k] = 0;
for(i = n-1; i > 0; i--) {
for(j = 0; j < gt[i]; j++) {
if(i == n-1) dp[i][j][a[i][j]] = 1;
int lx, ly, rx, ry, lv, rv;
lx = g[i][j][0][0], ly = g[i][j][0][1];
rx = g[i][j][1][0], ry = g[i][j][1][1];
lv = a[lx][ly], rv = a[rx][ry];
for(k = 0; k <= s; k++) {
if(dp[i][j][k] == 0) continue;
if(lx != -1) {
if(k + lv <= s)
dp[lx][ly][k+lv] += dp[i][j][k];
}
if(rx != -1) {
if(k + rv <= s)
dp[rx][ry][k+rv] += dp[i][j][k];
}
}
}
}
long long paths = 0;
for(i = 0; i < gt[0]; i++)
paths += dp[0][i][s];
printf("%lld\n", paths);
if(paths == 0) {puts("");continue;}
int sx = 0, sy = 0, ss = s;
for(i = 0; i < gt[0]; i++) {
if(dp[0][i][s]) {
sy = i;
break;
}
}
printf("%d ", sy);
while(sx != n-1) {
int lx, ly, rx, ry, v;
lx = vg[sx][sy][0][0], ly = vg[sx][sy][0][1];
rx = vg[sx][sy][1][0], ry = vg[sx][sy][1][1];
v = a[sx][sy];
if(lx != -1) {
if(dp[lx][ly][ss-v]) {
putchar('L');
sx = lx, sy = ly, ss = ss-v;
continue;
}
}
putchar('R');
sx = rx, sy = ry, ss = ss-v;
}
puts("");
}
return 0;
}