Помощь в проблеме ДП - PullRequest
Новая
       19

Помощь в проблеме ДП

5 голосов
/ 22 августа 2011

Я пытаюсь решить проблему из SPOJ ( link ), которую можно кратко описать так: Задано n интервалов, каждый с целым началом и концом, и задано конец с максимальным временем (давайте назовем это max_end), выясните, сколько способов вы можете выбрать набор интервалов, который охватывает 1 ... max_end. Интервалы могут перекрываться. Я попробовал DP; сначала сортировка по времени окончания, затем dp [i] - это пара, где dp [i] .first - это минимальное количество интервалов, необходимое для покрытия 1 ... end [i] , последнее использование интервала i и dp [i] .second - это количество способов сделать это. Вот мой основной цикл DP: 

for( int i = 1; i < n; i ++ ) {
    for( int j = 0; j < i; j ++ ) {
        if( ! ( x[ j ].end >= x[ i ].start - 1 ) )
            continue;
        if( dp[ j ].first + 1 < dp[ i ].first ) {
            dp[ i ].first = dp[ j ].first + 1;
            dp[ i ].second = dp[ j ].second;
        }
        else if( dp[ j ].first + 1 == dp[ i ].first ) {
            dp[ i ].second += dp[ j ].second;
        }
    }
}

К сожалению, это не сработало. Может кто-нибудь сказать, пожалуйста, где у меня ошибка? Заранее спасибо! :)

1 Ответ

1 голос
/ 22 сентября 2011

Я не уверен, что понял идею вашего решения, но я описываю свое решение AC:

Я использую функцию с запоминанием, но вы можете переписать ее, используя нерекурсивный DP.

Допустим, у нас есть интервалы в массиве

pair a [100];где [i] .first - начало интервала, а [i] .second - конец интервала.

Сортировать этот массив по begin first (поведение алгоритма сортировки stl по умолчанию с компаратором пар по умолчанию)).

Теперь представьте, что мы «ставим» интервалы один за другим от начала до конца.

let f (int x, int prev) возвращает количество способов завершить заполнение, если в данный момент последний интервал равен x, а предыдущий - «prev».

мы рассчитаем это следующим образом: 

int f(int x, int prev) {
  // if already calculated dp[x][prev], return it. Otherwise, calculate it
  if (dp[x][prev] != -1) {
    return dp[x][prev];
  }
  if (a[x].second == m) {
    return dp[x][prev] = 1; // it means - X is last interval in day
  }
  else {
    dp[x][prev] = 0;
    for (int i = x + 1; i < n; ++i) { // try to select next interval
      if (a[i].first <= a[x].second && // there must be not empty space after x interval
          a[i].second > a[x].second && // if this is false, the set won't be minimal - i interval is useless
          a[i].first > a[x].first && // if this is false, the set won't be minimal, x interval is useless
          a[prev].second < a[i].first) { // if this is false, the set won't be minimal, x interval is useless.  
        dp[x][prev] = (dp[x][prev] + f(i, x)) % 100000000;
      }
    }
  }
  return dp[x][prev];
}

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

for (int i = 0; i < n; ++i) {
  if (a[i].first == 0) {
     for (int j = i + 1; j < n; ++j) {
        if (a[j].first > 0 && // we don't need to start at 0 - in this case either i or j will be useless
            a[j].first <= a[i].second && // there must be no space after i interval
            a[j].second > a[i].second) { // in opposite case j will be useless
           res = (res + f(j, i)) % 100000000;
        }
     }
     // also we need to check the case when we use only one interval:
     if (a[i].second == m) {
        res = (res + 1) % 100000000;
     }
  }
}

После этого нам нужно только распечатать разрешение.

...