Проблема TopCoder FourBlocks - PullRequest
Новая
       11

Проблема TopCoder FourBlocks

1 голос
/ 15 февраля 2011

Приведенный ниже код является ответом на популярную проблему topcoder FourBlocks (Вам необходимо войти в систему). Решение использует запоминание битовой маски, чтобы найти максимальную сумму в сетке, используя блоки размером 1 и квадратный блок размера 4. Может кто-нибудь помочь мне понять, как это работает? Что это делает 

int[][] d = new int[m + 1][1 << n] // why 1<<n ?

Также, как функция rec () помещается в квадрат? его сравнивают только 2 бита. 

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;


public class FourBlocks
{
  int n;

  public int maxScore(String[] grid)
  {
    n = grid.length;
    int m = grid[0].length();
    int[][] d = new int[m + 1][1 << n];
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      int mask = 0;
      for (int j = 0; j < n; ++j) {
        if (grid[j].charAt(i) == '1') {
          mask |= 1 << j;
        }
      }
      ans += Integer.bitCount(mask);
      for (int j = 0; j < 1 << n; ++j) {
        if ((j & mask) == 0) {
          rec(0, j | mask, 0, d[i][j], d[i + 1]);
        }
      }
    }
    return d[m][0] + ans;
  }

  void rec(int i, int mask, int mask2, int sum, int[] d) {
    if (i == n) {
      d[mask2] = Math.max(d[mask2], sum);
      return;
    }
    rec(i + 1, mask, mask2, sum, d);
    if ((mask & (1 << i)) == 0) {
      rec(i + 1, mask, mask2, sum + 1, d);
    }
    if (i < n - 1 && (mask & (1 << i)) == 0 && (mask & (1 << (i + 1))) == 0) {
      rec(i + 2, mask, mask2 | (1 << i) | (1 << (i + 1)), sum + 16, d);
    }
  }


}

1 Ответ

1 голос
/ 22 февраля 2011

1<<n - это количество способов заполнить строку 1.(1<<n = 2 ^ n).Похоже, что он вычисляет все возможные способы заполнить доску 1, а затем проверяет, сколько четверок умещается. Чтобы ускорить его, он использует динамическое программирование, чтобы свернуть его от экспоненциального числа строк.

...