By yusijia

Updated:

Contents
  • 《算法竞赛入门经典》

不错的例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int a[11][101], d[11][101], nexts[11][101];

int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m;
    while(scanf("%d%d", &m, &n) != EOF){
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                scanf("%d", &a[i][j]);
            }
        }
        memset(d, 0, sizeof(d));
        memset(nexts, 0, sizeof(nexts));

        int ans = INF, first = 0;
        for(int j = n-1; j >= 0; j--){
            for(int i = 0; i <= m-1; i++){
                if(j == n-1)   d[i][j] = a[i][j]; // 最后一列状态初始化
                else{
                    int rows[3] = {i, i-1, i+1};    // 方向向量
                    if(i == 0)   rows[1] = m-1;
                    if(i == m-1) rows[2] = 0;
                    sort(rows, rows+3);             // 重新排序，以便找到字典序最小的

                    d[i][j] = INF;                  //初始化
                    for(int k = 0; k < 3; k++){
                        int v = d[rows[k]][j+1] + a[i][j];
                        if(v < d[i][j]){
                            d[i][j] = v;
                            nexts[i][j] = rows[k];  // 记录路径
                        }
                    }
                }
                if(j == 0 && d[i][j] < ans){        //找起点
                    ans = d[i][j];
                    first = i;
                }
            }
        }
        printf("%d", first + 1);
        int i = nexts[first][0];
        for(int j = 1; j < n; j++){
            printf(" %d", i+1);
            i = nexts[i][j];
        }
        printf("\n%d\n", ans);
    }
    return 0;
}
Contents