uva10564

제목의 대의: 제목에서 제시한 그림처럼 주세요.1층에서 맨 아래층으로 내려가야 하며 왼쪽 아래나 오른쪽 아래로만 내려가야 하며 지나간 숫자의 합은sum이다.-- S와 꼭 같은 경로의 합이 얼마나 되나.있다면, 출력 사전의 순서가 가장 작은 경로입니다.
사고방식: dp[i][j][k]는 좌표(i, j)에서 마지막 층으로 가는 것과 k로 할 방안의 수를 나타낸다.이것은 왼쪽 아래 또는 오른쪽 아래로만 갈 수 있기 때문에 dp[i][j][k]=dp[i+1][j][k-val]+dp[i+1][j+1][k-val]에서 val은 각각 좌표(i+1,j),(i+1,j+1)의 값을 나타낸다.나는 수출이 나에게 또 하나의 난제라고 생각한다.
코드:

#include <stdio.h>
#include <cstring>
#include <iostream>
using namespace std;

const int INF =0x3f3f3f3f;
int n,s;
int num[50][22];
long long dp[50][22][510];

void init() {
    for(int i = 1;i <= n; i++)
        for(int j = 1; j <=n - i + 1; j++)
            scanf("%d",&num[i][j]);
    for(int i = n + 1; i <= 2 * n -1; i++)
        for(int j = 1; j <= i + 1 - n; j++)
            scanf("%d",&num[i][j]);
}

void print(int i,int j,int sum) {
    if(i >= 2 * n - 1)
        return;
    int val = num[i][j];
    if(i < n) {
        if(j > 1 && dp[i + 1][j - 1][sum - val]) {
            printf("L");
            print(i + 1, j -1,sum - val);
            return;
        }
        printf("R");
        print(i + 1, j, sum - val);
    }
    else {
        if(dp[i + 1][j][sum - val]) {
            printf("L");
            print(i + 1, j, sum - val);
            return;
        }
        printf("R");
        print(i + 1, j + 1,sum - val);
    }
}
int main() {

    while(scanf("%d %d",&n,&s) && n + s) {
        init();
        memset(dp,0,sizeof(dp));

        for(int i = 1; i <= n; i++)
            dp[2 * n - 1][i][num[2 * n -1][i]] = 1;
        for(int i = 2 * n -2; i >= n; i--) {
            for(int j = 1; j <= i + 1 - n; j++)
                for(int v = num[i][j];v <= s; v++) {
                    int w = num[i][j];
                    dp[i][j][v] = dp[i + 1][j][v - w] + dp[i + 1][j + 1][v - w];
                }
        }
        long long ans = 0;
        for(int i = n - 1; i >= 1; i--) {
            for(int j  =1; j <= n - i + 1; j++) {
                for(int v = num[i][j]; v <= s; v++) {
                    int w = num[i][j];
                    if(j > 1) dp[i][j][v] += dp[i + 1][j - 1][v - w];
                    if(j < n - i + 1) dp[i][j][v] += dp[i + 1][j][v - w];
                }

            if(i == 1)
                ans += dp[1][j][s];
            }
        }
        printf("%lld
",ans);
        for(int i = 1; i <= n; i++) {
            if(dp[1][i][s]) {
                printf("%d ", i -1);
                print(1,i,s);
                break;
            }
        }
        printf("
");
    }
    return 0;
}