9-4 Unidirectional TSP uva116 （DP）

　　题意：给一个n行m列矩阵从第一列任意一个位置出发每次往右右上右下三个方向走一格直到最后一列输出所类和的最小值和路径！！最小值相同则输出字典序最小路径

很像一开始介绍的三角形dp 很明显用dp来做

但是输出路径非常麻烦

要使路径为最小字典序对三个方向进行选择时应该从小到大这样就会是最小字典序

我一开始用一维的next数组这样答案是不连续的可能从1跳到5

应该用二维的next数组！！！！

#include<bits/stdc++.h>

using namespace std;

#define N 2000+5

#define inf 0x3f3f3f3f

int n,m;

int dp[N][N];

int next1[N][N];

int mp[N][N];

int first;

int main()

{

    while(scanf("%d%d",&n,&m)==&&(m+n))

    {

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

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

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

        int ans=inf;

        memset(next1 ,,sizeof next1);

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

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

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

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

        {

            int dic[]={i-,i,i+};

            if(i==)dic[]=n;

            if(i==n)dic[]=;

            sort(dic,dic+);

            dp[i][j]=inf;

            for(int k=;k<;k++)

            {

                if(dp[i][j]>mp[i][j]+dp[dic[k] ][j+])

                {

                    dp[i][j]=mp[i][j]+dp[dic[k] ][j+];

                    next1[i][j]=dic[k];

                }

                if(j==)

              {

                  if(ans>dp[i][j])

                  {

                  ans=dp[i][j];

                  first=i;

                  }

              }

            }

        }

       printf("%d",first);

       for(int i=next1[first][],j=;j<=m;i=next1[i][j],j++)

         printf( " %d",i);

        printf("\n%d\n",ans);

    }

    return ;

}

巴特西

9-4 Unidirectional TSP uva116 （DP）

最新文章

热门文章