# Sign-up Thread: Problem Solving #1

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 01-26-2003
Nick
Quote:

I 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.
I think this is the correct answer but I coded it sort of
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; }```
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12