tyvj1124

tyvj1124.cpp

/*
Problem: Tyvj 1124
Author: Cheng Luyu
Date: 2014/8/1 pm
*/
#include <cstdio>
#include <cstdlib>

const int N = 100, M = 100;

enum direction {
  Empty = 0, Start, Left, Up, LeftUp
};

int n, m, w[M][N], f[M][N]; // m kinds of flower, n pots
direction record[M][N];

inline int max(int x, int y) {
  return x > y ? x : y;
}

void debug(int t[M][N]) {
  putchar('\n');
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++)
      printf("%d\t", t[i][j]);
    putchar('\n');
  }
}

void debug_path() {
  putchar('\n');
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      char ch;
      switch (record[i][j]) {
        case Start: ch = '*'; break;
        case Left: ch = '-'; break;
        case Up: ch = '|'; break;
        case LeftUp: ch = '\\'; break;
        default: ch = ' '; break;
      }
      printf("%c ", ch);
    }
    putchar('\n');
  }
}

void read() {
  scanf("%d%d", &m, &n);
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      scanf("%d", &w[i][j]);
}

void solve() {
  f[0][0] = w[0][0];
  record[0][0] = Start;
  for (int i = 1; i < n; i++) {
    f[0][i] = w[0][i];
    if (f[0][i] < f[0][i - 1]) {
      f[0][i] = f[0][i - 1];
      record[0][i] = Left;
    } else {
      record[0][i] = Start;
    }
  }

  for (int i = 1; i < m; i++)
    for (int j = i; j < n; j++) {
      if (f[i - 1][j] > f[i - 1][j - 1] + w[i][j]) {
        f[i][j] = f[i - 1][j];
        record[i][j] = Up;
      } else {
        f[i][j] = f[i - 1][j - 1] + w[i][j];
        record[i][j] = LeftUp;
      }

      if (f[i][j] < f[i][j - 1]) {
        f[i][j] = f[i][j - 1];
        record[i][j] = Left;
      }
    }
}

void print_path(int i = m - 1, int j = n - 1) {
  if (record[i][j] == Up) {
    
  }
}

void print_answer() {
  debug(f);
  debug_path();
  printf("%d\n", f[m - 1][n - 1]);
}

int main() {
  read();
  solve();
  print_answer();
  return 0;
}
/*
3 5 
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

*/

2014-8-1 17:33:36
Code remains unfinished.