4112377_mle.cc

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

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

using namespace std;

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

int main()
{
	short n, m;
	short i, j;
	short p, q;

	scanf("%d%d", &n, &m);
	for (i = 0; i < m; i++)
	{
		scanf("%d", &fee[0][i]);
		dp[0][i] = fee[0][i];
		prev[0][i] = -1;
	}
	p = 1;q = 0;
	for (i = 1; i < n; i++, p = !p, q = !q)
	{
		for (j = 0; j < m; j++)
		{
			scanf("%d", &fee[p][j]);
		}
		for (j = 0; j < m; j++)
		{
			dp[p][j] = dp[q][j] + fee[p][j];
			prev[i][j] = j;
		}
		int tmp;
		for (j = 1; j < m; j++)
		{
			tmp = dp[p][j - 1] + fee[p][j];
			if (dp[p][j] > tmp)
			{
				dp[p][j] = tmp;
				prev[i][j] = j - 1;
			}
		}
		for (j = m - 2; j >= 0; j--)
		{
			tmp = dp[p][j + 1] + fee[p][j];
			if (dp[p][j] > tmp)
			{
				dp[p][j] = tmp;
				prev[i][j] = j + 1;
			}
		}
	}
	ans.clear();
	int min = 2000000000;
	int st;
	for (i = 0; i < m; i++)
	{
		if (dp[q][i] < min)
		{
			min = dp[q][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;
}