I think this is the correct answer but I coded it sort ofI got this question from a guy named oskillian. You can find him on flashdaddee. I'm pretty sure he has the correct answer for this, so if it's bugging you, post something there.

sloppy.

Code:#include <iostream> using std::cerr; using std::cout; using std::endl; #include <fstream> using std::ifstream; using std::ofstream; const int MAX_M = 200; const int MAX_N = 200; const int COST_INF = 100000; int M, N; void load_file(const char* filename); void print_results(const char* filename); int find_optimal(); int C[MAX_M][MAX_N]; int S[MAX_M][MAX_N]; int main(void) { load_file("HOTEL.IN"); cout << "optimal = " << find_optimal() << endl; print_results("HOTEL.OUT"); return 0; } void load_file(const char* filename) { ifstream in(filename); if (!in) { cerr << "Error opening file" << endl; exit(EXIT_FAILURE); } in >> N; in >> M; int rn, cn, c; for (int i = 0; i < M * N; ++i) { in >> rn; in >> cn; in >> c; C[cn - 1][rn - 1] = c; } } int find_optimal() { int T[MAX_M + 1][MAX_N + 1]; int m, m_k; for (int i = 0; i < M; ++i) { T[i][N] = -COST_INF; } for (int i = 0; i <= N; ++i) { T[M][i] = 0; } for (int i = M - 1; i >= 0; --i) { for (int j = N - 1; j >= 0; --j) { m = -COST_INF; for (int k = j; k < N; ++k) { int t = C[i][k] + T[i + 1][k + 1]; if (t > m) { m = t; m_k = k; } } T[i][j] = m; S[i][j] = m_k; } } return T[0][0]; } void print_results(const char* filename) { ofstream out(filename); int n = 1; int j, jp; int zn; if (!out) { cerr << "Error opening output file" << endl; exit(EXIT_FAILURE); } j = -1; zn = 0; for (int i = 0; i < M; ++i) { j = S[i][j + 1]; for (int k = zn; k < j; ++k) out << 0 << endl; zn = j + 1; out << n << endl; n++; } for (int k = zn; k < N; ++k) out << 0 << endl; }