紫书 例题 9-4 UVa 116 ( 字典序递推顺序）

这道题在递推方式和那个数字三角形有一点相像，很容易推出来

但是这道题要求的是字典序，这里就有一个递推顺序的问题

这里用逆推，顺推会很麻烦，为什么呢？

如果顺推的话，最后一行假设有种情况是最小值，那么你怎么知道哪一种的

是字典序最小？最后一行的数字最小显然不一定整个路径的字典序最小，因为

字典序是从第一行开始比较的。

如果非要这么做的话可以把这几种情况的路径全部记下来，

然后排序，选出最小的输出。同时输出路径还要写一个递归。这样显然很麻烦。

但是如果是逆推的话，我们推到最后是第一行，这个时候如果有多种情况是

最小值，显然第一行最小肯定字典序最小，这个时候就可以选出答案，直接

输出就可以了。

所以以后这种要求字典序的题要考虑逆推

#include<cstdio>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

int a[MAXN][MAXN], d[MAXN][MAXN], Next[MAXN][MAXN];

int n, m;

int main()

{

	while(~scanf("%d%d", &n, &m))

	{

		REP(i, 0, n)

			REP(j, 0, m)

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

		int ans = 1e9, first = 0;

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

			REP(i, 0, n)

			{

				if(j == m - 1) d[i][j] = a[i][j];

				else

				{

          			int row[3] = {i, (i - 1 + n) % n, (i + 1) % n};

         		 	d[i][j] = 1e9;

					sort(row, row + 3);

					REP(k, 0, 3)

					{

						int v = a[i][j] + d[row[k]][j+1];

						if(v < d[i][j]) { d[i][j] = v; Next[i][j] = row[k]; }

					}

				}

				if(j == 0 && d[i][j] < ans) { ans = d[i][j]; first = i; }

			}

		printf("%d", first + 1);

		for(int i = Next[first][0], j = 1; j < m; i = Next[i][j], j++)

			printf(" %d", i + 1);

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

	}

	return 0;

}