https://cn.vjudge.net/problem/UVA-116
题意:给出m行n列的整数矩阵,从第一列任何一个位置出发每次往右,右上或右下走一格,最终到达最后一列,要求经过的整数之和最小。
#include<iostream>
#include<algorithm>
using namespace std; const int INF = 0x7FFFFFFF;
const int maxn = + ; int m, n;
int a[maxn][maxn];
int dp[maxn][maxn];
int next[maxn][maxn]; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
while (cin >> m >> n && m && n)
{
for (int i = ; i < m;i++)
for (int j = ; j < n; j++)
cin >> a[i][j];
int first = ;
int ans = INF;
for (int j = n - ; j >= ; j--)
{
for (int i = ; i < m; i++)
{
if (j == n - ) dp[i][j] = a[i][j]; //边界
else
{
dp[i][j] = INF;
int row[] = { i, i + , i - };
if (i == ) row[] = m - ;
if (i == m - ) row[] = ;
sort(row, row + ); //重新排序,以便找到字典序最小的
for (int k = ; k < ; k++)
{
int v = dp[row[k]][j + ] + a[i][j];
if (v < dp[i][j]) { dp[i][j] = v; ::next[i][j] = row[k];}
}
}
if (j == && dp[i][j] < ans) {
ans = dp[i][j]; first = i;
}
}
}
cout << first + ;
for (int i = ::next[first][], j = ; j < n; i = ::next[i][j], j++)
cout << " " << i + ;
cout << endl << ans << endl;
}
return ;
}