define _CRT_SECURE_NO_WARNI NGS include iostream include vector includ

 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
#define eps 1e-6
#define Cout cout << fixed << setprecision(2)
#define vd vector<double>
using namespace std;
int n, m, inf = 1000000000;
struct v2{
int cost;
vector<int> pred;
v2() {}
v2(int _cost) : cost(0) {}
};
vector<vector<v2> > dp;
int map[100][500] = { 0 };
int main(){
//freopen("input.txt", "r", stdin);
//freopen( "output.txt", "w", stdout);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
cin >> map[i][j];
}
dp.resize(n, vector<v2>(m, v2(inf)));
for (int i = 0; i < m; ++i){
dp[0][i].cost = map[0][i];
dp[0][i].pred.push_back(i + 1);
}
for (int i = 1; i < n; ++i) {
for (int j = 0; j < m; ++j) {
dp[i][j].cost = dp[i - 1][j].cost + map[i][j];
dp[i][j].pred = dp[i - 1][j].pred;
dp[i][j].pred.push_back(j + 1);
}
for (int j = 0; j < m - 1; ++j) {
if (dp[i][j + 1].cost < dp[i][j].cost + map[i][j]) {
dp[i][j].cost = dp[i][j + 1].cost + map[i][j];
dp[i][j].pred = dp[i][j + 1].pred;
dp[i][j].pred.push_back(j + 1);
}
}
for (int j = m - 1; j > 0; --j) {
if (dp[i][j - 1].cost < dp[i][j].cost + map[i][j]) {
dp[i][j].cost = dp[i][j - 1].cost + map[i][j];
dp[i][j].pred = dp[i][j - 1].pred;
dp[i][j].pred.push_back(j + 1);
}
}
if (dp[i][1].cost < dp[i][0].cost + map[i][0]) {
dp[i][0].cost = dp[i][1].cost + map[i][0];
dp[i][0].pred = dp[i][1].pred;
dp[i][0].pred.push_back(1);
}
}
int id = 0;
int minn = dp[n - 1][0].cost;
for (int i = 0; i < m; ++i) {
if (dp[n - 1][i].cost < minn) {
minn = dp[n - 1][i].cost;
id = i;
}
}
for (int i = 0; i < dp[n - 1][id].pred.size(); ++i) {
cout << dp[n - 1][id].pred[i] << " ";
}
return 0;
}