uva 10564 - Paths through the Hourglass 沙漏里的路径（类似01背包问题）

小灰灰 2021-12-09 02:59 155阅读 0赞

## 题意：给出一个沙漏形状的2（n - 1)行矩阵，并给出一个总全值和每个坐标的权值，每个位置可以走向下一行与它相邻的两个或一个位置（参见题目中的图），请找出有多少调路径上的权值和等于给定的总权值，并输出字典序最小的一条路径的起始位置 和方案。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][] ##

## 分析：数字三角的升级版，本题需要记录每个点所有能出现的情况，所以开一个三维数组，dp\[i\]\[j\]\[k\]表示在i,j这个位置权值和为k的走法有多少种，状态转移公式dp\[i\]\[j\]\[k\] = dp\[i+1\]\[j\]\[k - num\[i\]\[j\]\] + dp\[i + 1\]\[j + 1\]\[k - num\[i\]\[j\]\]，因为字典序最小，所以自底向上进行数字三角形上的01背包，递归打印路径。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 50;
    ll dp[N][N][510];
    int n, s, str[N][N];
    int abs(int x){ return x<0?-x:x; }
    void printf_ans(int x, int y, int v)
    {
        if(x==2*n-1) return ;
        int ss = str[x][y];
        if(dp[x+1][y][v-ss]) { printf("L"); printf_ans(x+1,y,v-ss); }
        else { printf("R"); printf_ans(x+1,y+1,v-ss); }
    }
    int main ()
    {
        while(scanf("%d %d",&n, &s), s+n)
        {
            for(int i = 1; i <= n; i++)
                for(int j = i; j <= n; j++)
                    scanf("%d",&str[i][j]);
            for(int i = n+1; i <= 2*n-1; i++)
                for(int j = n; j <= i; j++)
                    scanf("%d",&str[i][j]);
            memset(dp,0,sizeof(dp));
            for(int i = n; i <= 2*n-1; i++)
                dp[2*n-1][i][str[2*n-1][i]] = 1;
            for(int i = 2*n-2; i >= n; i--)
                for(int j = n; j <= i; j++)
                    for(int v = str[i][j], k = str[i][j]; k <= s; k++)
                        dp[i][j][k] = dp[i+1][j][k-v]+dp[i+1][j+1][k-v];
            for(int i = n-1; i >= 1; i--)
                for(int j = i; j <= n; j++)
                    for(int v = str[i][j], k = str[i][j]; k <= s; k++)
                        dp[i][j][k] = dp[i+1][j][k-v]+dp[i+1][j+1][k-v];
            long long ans = 0;
            for(int i = 1; i <= n; i++) ans+=dp[1][i][s];
            printf("%lld\n", ans);
            for(int i = 1; i <= n; i++) if(dp[1][i][s])
            {
                printf("%d ",i-1);
                printf_ans(1,i,s);
                break;
            }
            printf("\n");
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20211209/ba3a4c801c3f46fa8fb5633b9cbfe6b6.png