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;
}