uva 116 数塔动态规划

亦凉 2022-08-03 13:41 203阅读 0赞

横着的数塔，从左往右走，可以走右上，右，右下三个方向，最后一行往右下走可以穿越到第一行，第一行往右上走可以穿越到最后一行。

最后要求输出走的路径以及路径和的最小值，如果存在多种路径，输出字典序最小的那个。

输出路径的字典序最小，要从右往左加，加的时候记录路径，这样可以使得路径的字典序最小，如果从左往右加的话最后一列如果有多个相同的最小值，不能确定那一条路径的字典序最小，他们可能是按照不同的路径过来的。所以要从右往左加。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline ll in()
    {
        ll res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    ll dp[111][111];
    int path[111][111];
    
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            mem(dp,0);
            mem(path,0);
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    scanf("%lld",&dp[i][j]);
                }
            }
            if(n==1)  //下面的处理不了n==1的情况，，，，，
            {
                ll ans=0;
                for(int i=1;i<=m;i++)ans+=dp[1][i];
                for(int i=1;i<m;i++)putchar('1'),putchar(' ');
                puts("1");
                cout<<ans<<endl;
                continue;
            }
            for(int j=m-1;j>=1;j--)
            {
                for(int i=1;i<=n;i++)
                {
                    if(i==1)
                    {
                        if(dp[i][j+1]<=dp[n][j+1] && dp[i][j+1]<=dp[i+1][j+1])   //优先判断最小的
                        {
                            dp[i][j]+=dp[i][j+1];
                            path[i][j]=1;
                        }
                        else if(dp[i+1][j+1]<=dp[n][j+1] && dp[i+1][j+1]<=dp[i][j+1])//在判断次小的
                        {
                            dp[i][j]+=dp[i+1][j+1];
                            path[i][j]=i+1;
                        }
                        else dp[i][j]+=dp[n][j+1],path[i][j]=n;//判断最大的
                    }
                    else if(i==n)
                    {
                        if(dp[1][j+1]<=dp[i][j+1] && dp[1][j+1]<=dp[i-1][j+1])
                        {
                            dp[i][j]+=dp[1][j+1];
                            path[i][j]=1;
                        }
                        else if(dp[i-1][j+1]<=dp[1][j+1] && dp[i-1][j+1]<=dp[i][j+1])
                        {
                            dp[i][j]+=dp[i-1][j+1];
                            path[i][j]=i-1;
                        }
                        else dp[i][j]+=dp[i][j+1],path[i][j]=i;
                    }
                    else
                    {
                        if(dp[i-1][j+1]<=dp[i][j+1] && dp[i-1][j+1]<=dp[i+1][j+1])
                        {
                            dp[i][j]+=dp[i-1][j+1];
                            path[i][j]=i-1;
                        }
                        else if(dp[i][j+1]<=dp[i-1][j+1] && dp[i][j+1]<=dp[i+1][j+1])
                        {
                            dp[i][j]+=dp[i][j+1];
                            path[i][j]=i;
                        }
                        else dp[i][j]+=dp[i+1][j+1],path[i][j]=i+1;
                    }
                }
            }
    
            ll ans=10000000000000;
            int pos;
            for(int i=1;i<=n;i++)
            {
                if(dp[i][1]<ans)
                {
                    ans=dp[i][1];
                    pos=i;
                }
            }
            printf("%d%c",pos,m==1?'\n':' ');
            for(int i=1;i<m-1;i++)
            {
                printf("%d ",path[pos][i]);  //路径还原
                pos=path[pos][i];
            }
            if(m>1)printf("%d\n",path[pos][m-1]);//不要重复输出了
    
            cout<<ans<<endl;
    
        }
        return 0;
    }