企业官网建设流程全解析

1. 最后一列初始化错误（最致命）

UVA116 要求从第一列任意行出发，到达最后一列任意行结束。因此最后一列的dp[i][m-1]应该等于a[i][m-1]，表示从该位置到终点的最小和就是它本身。
你的代码：

cpp

for (int i=0;i<n-1;i++) dp[i][m-1]=INF; dp[n-1][m-1]=a[n-1][m-1];

这相当于强制路径必须走到最后一行结束，其他行无法到达终点，所以整个 DP 都是错的。

修正：

cpp

for (int i = 0; i < n; i++) dp[i][m-1] = a[i][m-1];

2. 起点选择错误

你直接从x=0开始输出路径，并认为起点是第 0 行。但最优路径的起点不一定是第 0 行。应该遍历第一列，找出dp[i][0]最小的行；如果有多行最小值相同，选择行号最小的那个（因为题目要求字典序最小）。

修正：

cpp

int start = 0; for (int i = 1; i < n; i++) { if (dp[i][0] < dp[start][0]) start = i; } // 如果值相等，因为 i 从小到大遍历，自然保留行号小的

3. 路径查找时数组越界

你在查找下一步时：

cpp

if (dp[x+i][j+1]+a[x][j]==dp[x][j]) { x=get_row(x+i); break; }

这里x+i可能为 -1 或 n，直接访问dp[-1][j+1]或dp[n][j+1]会越界。应该用get_row(x+i)计算实际行号。

修正：

cpp

int next_row = get_row(x+i); if (dp[next_row][j+1] + a[x][j] == dp[x][j]) { ... }

4. 字典序最小未处理

题目要求如果有多条最小路径，输出行号序列字典序最小的。你的查找顺序是i = -1, 0, 1，对应的行号是(x-1+n)%n, x, (x+1)%n，这不是按行号从小到大排列的。例如n=5, x=0，候选行号为4, 0, 1，实际大小顺序是0, 1, 4。你应该先对三个候选行号排序，然后按从小到大检查。

修正：

cpp

int rows[3] = {get_row(x-1), x, get_row(x+1)}; sort(rows, rows+3); for (int k = 0; k < 3; k++) { int nr = rows[k]; if (dp[nr][j+1] + a[x][j] == dp[x][j]) { x = nr; break; } }

5. 最终输出错误

你的输出：

cpp

cout<<n<<'\n'<<dp[0][0]<<'\n';

这里n是行数，不是最后一列的行号；dp[0][0]也不是最小和（因为起点可能不是第 0 行）。应该在循环输出完前m-1列后，输出最后一列的行号x+1，然后输出dp[start][0]。

修正：

cpp

// 循环输出前 m-1 列的行号 for (int j = 0; j < m-1; j++) { cout << x+1 << ' '; // ... 更新 x ... } cout << x+1 << '\n'; // 输出最后一列的行号 cout << dp[start][0] << '\n'; // 输出最小和