Memoized Log Cutting(Complete)

readme.md

Memoized Log Cutting(Complete)

Created with <3 with dartpad.dev.

main.dart

import 'dart:math';

void main() {
//     final p = [ 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 32, 35, 39, 43, 43, 45, 49, 50, 54, // 1X's
//           57, 60, 65, 68, 70, 74, 80, 81, 84, 85, // 2X's
//           87, 91, 95, 99, 101, 104, 107, 112, 115, 116, // 3X's
//           119, 121, 125, 129, 131, 134, 135, 140, 143, 145, // 4X's
//           151
//     ];
  
  final p = [0, 2, 11, 15, 22, 30, 32, 35, 37, 38, 39, 48, 51, 58, 63, 67, 76, 82, 87, 88, 98, 99, 101, 102, 110, 112, 117, 123, 125, 129, 130, 134, 141, 147, 149, 151, 157, 159, 163, 169, 170, 178, 186, 194, 197, 206, 216, 217, 220, 221];
  int n = 34; // 202
//   print(cutLog(p, n));
  final ss = cutLog(p, n);
  print(ss);
//   final ss2 = cutLogReal(p, 26);
//   print(ss2);
//   final ss3 = cutLogReal(p, 9);
//   print(ss2 + ss3);
}

int cutLog(List<int> p, int n) {
  var q = p[n];
//   print('q : $q');
  final listHistory = <int, int>{};
  for (int j = 0; j <= n; j++) {
    for (int i = 0; i <= j; i++) {
      final subtitudIndex = i + j; 
      var valuePi = p[i] < (listHistory[i] ?? 0) ? (listHistory[i] ?? 0) : p[i];
      var valuePj = p[j] < (listHistory[j] ?? 0) ? (listHistory[j] ?? 0) : p[j];
      final currSubValue = valuePi + valuePj;

      if (
        (listHistory.keys.any((e) => e == subtitudIndex) 
          && (listHistory[subtitudIndex] ?? 0) < currSubValue) || 
        (listHistory[subtitudIndex] ?? 0) == 0
      ) {
        print('${listHistory[subtitudIndex]} = $currSubValue');
        listHistory[subtitudIndex] = currSubValue;
      }

      if (subtitudIndex == n) {
        if (valuePi < (listHistory[i] ?? 0)){
          valuePi = listHistory[i] ?? 0;
        }

        if (valuePj < (listHistory[j] ?? 0)){
          valuePj = listHistory[j] ?? 0;
        }
        print('$i + $j = ${valuePi + valuePj}');
        q = max(q, valuePi + valuePj);
      }

      if (subtitudIndex < n) {
        continue;
      }
    }
  }
//   for (final ii in listHistory.entries) {
     
//   }

  return q;
}