4112174_mle.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 80 行

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int fee[100][500];
int dp[100][500];
int prev[100][500];
vector <int> ans;

int main()
{
	int n, m;
	int i, j;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			prev[i][j] = -1;
			scanf("%d", &fee[i][j]);
		}
	}
	for (i = 0; i < m; i++)
	{
		dp[0][i] = fee[0][i];
	}
	for (i = 1; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			dp[i][j] = dp[i - 1][j] + fee[i][j];
			prev[i][j] = j;
		}
		int tmp;
		for (j = 1; j < m; j++)
		{
			tmp = dp[i][j - 1] + fee[i][j];
			if (dp[i][j] > tmp)
			{
				dp[i][j] = tmp;
				prev[i][j] = j - 1;
			}
		}
		for (j = m - 1; j >= 0; j--)
		{
			tmp = dp[i][j + 1] + fee[i][j];
			if (dp[i][j] > tmp)
			{
				dp[i][j] = tmp;
				prev[i][j] = j + 1;
			}
		}
	}
	ans.clear();
	int min = 2000000000;
	int st;
	for (i = 0; i < m; i++)
	{
		if (dp[n - 1][i] < min)
		{
			min = dp[n - 1][i];
			st = i;
		}
	}
	int row = n - 1;
	while (st != -1)
	{
		ans.push_back(st + 1);
		if (st == prev[row][st])
			row--;
		else
			st = prev[row][st];
	}
	for (i = ans.size() - 1; i >= 0; i--)
		printf("%d\n", ans[i]);
	return 0;
}