hdu5092 dp（递推）

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5092

题意：给一个m*n的矩阵，找到一个纵向的"线"使得线上的和最小并输出这条线，线能向8个方向

延伸，要求找的是纵向的一条线(每一行各取一个点连成一线) ，输出路径，若有多条路径，输出最

靠右的。

注意!! 最靠右的意思是，从上往下最靠右的，是连成一条线上字典序是最大的！！ 字典序！！！  eg（3,1,3）<（3，2,1）

好不容易自己想出来一道题 还因为字典序没搞懂一直WA。

字典序最大那么久要从下往上dp，找最小值里面最右面的，记录路径。这样就比较容易理解了。

具体见代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

int mp[][];

int dp[][],path[][];

int d[];

int m,n;

int main()

{

    int T;

    scanf("%d",&T);

    for(int p=; p<=T; p++)

    {

        scanf("%d%d",&m,&n);

        for(int i=; i<=m; i++)

            for(int j=; j<=n; j++)

                scanf("%d",&mp[i][j]);

        memset(dp,,sizeof(dp));

        memset(path,,sizeof(path));

        for(int i=; i<=n; i++)

            dp[m][i]=mp[m][i];

        for(int i=; i<=n; i++)

            for(int i=m-; i>=; i--)

            {

                int maxx;

                for(int j=; j<=n; j++)

                {

                    if(j==)

                    {

                        maxx=dp[i+][j],path[i][j]=j;

                        if(dp[i+][j+]<=dp[i+][j]) maxx=dp[i+][j+],path[i][j]=j+;

                    }

                    else if(j==n)

                    {

                        maxx=dp[i+][j-],path[i][j]=j-;

                        if(dp[i+][j]<=dp[i+][j-]) maxx=dp[i+][j],path[i][j]=j;

                    }

                    else

                    {

                        maxx=dp[i+][j-],path[i][j]=j-;

                        if(dp[i+][j]<=maxx) maxx=dp[i+][j],path[i][j]=j;

                        if(dp[i+][j+]<=maxx) maxx=dp[i+][j+],path[i][j]=j+;

                    }

                    dp[i][j]=mp[i][j]+maxx;

                }

            }

        int minn=dp[][],k=;

        for(int i=; i<=n; i++)

            if(dp[][i]<=minn)

                minn=dp[][i],k=i;

        printf("Case %d\n",p);

        memset(d,,sizeof(d));

        int pt=k,t=;

        d[]=k;

        for(int i=; i<m; i++)

        {

            pt=path[i][pt];

            d[++t]=pt;

        }

        for(int i=; i<t; i++)

            printf("%d ",d[i]);

        printf("%d\n",d[t]);

    }

    return ;

}