Где здесь ошибка в моем подходе к дп?https://www.spoj.com/problems/AE00/

Question

Проблема:

У Байтмена есть коллекция из N квадратов со стороной 1. Сколько разных прямоугольников он может сформировать, используя эти квадраты?

Два прямоугольника считаются разными, если ни один изих можно вращать и перемещать для получения второго.Во время построения прямоугольника Байтмен не может ни деформировать квадраты, ни ставить какие-либо квадраты на любые другие.

Входные данные В первой и единственной строке стандартного ввода содержится одно целое число N (1 <= N <= 10000). </p>

Выходные данные Первая и единственная строка стандартного выходного сигнала должна содержать одно целое число, равное количеству различных прямоугольников, которые Байтмен может сформировать, используя свои квадраты.

Пример Для входных данных: 6

правильный результат: 8

Мое решение:

public class Rectangles {
    public void solve(int testNumber, Reader in, OutputWriter out) {
        try {
            while(true) {
                int N = in.ni();
                out.printLine(result(N));
            }
        } catch (Exception ee) { }
    }

    private long result(int n) {
        long[] res = new long[n+2];
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        for(int i=3;i<=n;i++) {
            if(i%2 == 0) {
                res[i] = 3 + res[i-2];
            } else {
                res[i] = 1 + res[i-1];
            }
        }
        return res[n];
    }
}

Мой подход DP:

For 0 squares: Result is 0
For 1 square: Result is 1: f(1) = 1
For 2 squares: Result is 2 : f(2) = 2
Now for f(3) = f(2) + 1 more square
With 1 more square we can only place it horizontally and hence 
f(3) = f(2)+1, generalizing, when n is ODD : f(n) = f(n-1) + 1
when n is EVEN: we use two squares which can make up to 3 rectangles, two horizontally([SQ] & [SQ][SQ]) plus one on top of the other, so total 3 possibilities, and hence f(n) when n is EVEN: f(n) = f(n-2) + 3.

Answer 1

Для данного N все возможные различные прямоугольники:

  1x1 1x2 1x3 1x4 ... 1x[N/1]
      2x2 2x3 2x4 ... 2x[N/2] // 2x1 is equals to 1x2 
          3x3 3x4 ... 3x[N/3] // 3x1 and 3x2 are equal to 1x3 and 2x3
                  ... 
                      Mx[N/M]   

Где [...] означает целую часть (floor) или, другими словами, [N/M] равно целочисленное деление . Так как N не очень большой, мы можем просто зациклить

C # Код:

private static int Solution(int value) {
  int result = 0;

  for (int i = 1; ; ++i) {
    int upTo = value / i;

    if (i > upTo)
      return result;

    result += (upTo - i + 1);
  }
}

Демо:

  int[] tests = new int[] {
    0,
    1,
    6,
    9,
    10000,
  };

  string report = string.Join(Environment.NewLine, tests
    .Select(test => $"{test,5} -> {Solution(test),5}"));

  Console.Write(report);

Результат:

    0 ->     0
    1 ->     1
    6 ->     8
    9 ->    13
10000 -> 46884

Answer 2

Не все прямоугольники получаются путем добавления одного квадрата к существующему прямоугольнику.

Например, если N = 9, один из прямоугольников равен 3x3.Ваш подход DP не найдет его.Или, другими словами, f (9)> f (8) + 1.

Answer 3

Я предлагаю рассмотреть, сколько прямоугольников с меньшей (!) Стороной длины x может существовать.Затем переберите все возможные значения для x и суммируйте их. Псевдокод:

result = 0
for x in 1 .. floor(sqrt(n)):
  result += number_of_rectangles_with_smaller_side(x)

И я думаю, number_of_rectangles_with_smaller_side(x) - это floor(n / x) - x + 1, но вы должны проверить это дважды; -)