Удаление рекламных щитов из данных

Ответ 1

Это типичная проблема с DP. Допустим, что P (n, k) является максимальной прибылью от того, что k рекламных щитов до позиции n на дороге. Тогда у вас есть следующая формула:

 P(n,k) = max(P(n-1,k), P(n-1,k-1) + C(n))
 P(i,0) = 0 for i = 0..n

Где c (n) - это прибыль от размещения n-го рекламного щита на дороге. Используя эту формулу для вычисления P (n, k) снизу вверх, вы получите решение в O (nk) времени.

Я оставлю вас, чтобы понять, почему эта формула держится.

изменить

Данг, я неправильно понял вопрос.

Это все еще проблема DP, просто формула отличается. Скажем, что P (v, i) означает максимальную прибыль в точке v, где последний кластер биллбордов имеет размер i. Тогда P (v, i) можно описать, используя следующие формулы:

P(v,i) = P(v-1,i-1) + C(v) if i > 0 
P(v,0) = max(P(v-1,i) for i = 0..min(k, v)) 
P(0,0) = 0

Вам нужно найти max(P(n,i) for i = 0..k)).

Ответ 2

Эта проблема является одной из проблем, опубликованных на сайте www.interviewstreet.com...

Я рад сказать, что недавно получил это, но не совсем удовлетворен и хотел посмотреть, есть ли там лучший способ.

Решение soulcheck DP выше прямолинейно, но не сможет полностью решить это из-за того, что K может быть большим, чем N, что означает, что сложность DP будет O (NK) как для времени выполнения, так и для пространства.

Другим решением является выполнение ветвей и границ, отслеживание наилучшей суммы до сих пор и обрезание рекурсии, если на некотором уровне, то есть, если currSumSoFar + SUM (a [currIndex..n)) <= bestSumSoFar... затем немедленно выйдите из функции, без дальнейшей обработки, когда верхняя граница не будет бить лучшую сумму до сих пор.

Приведенная выше ветвь и граница были приняты тестером для всех, кроме 2 тестовых случаев. К счастью, я заметил, что два тестовых случая используют небольшой K (в моем случае K < 300), поэтому DP-метод O (NK) достаточен.

Ответ 3

soulcheck (second) Решение DP является правильным в принципе. Есть два улучшения, которые вы можете сделать с помощью этих наблюдений:

1) Нет необходимости выделять всю таблицу DP. Вы всегда смотрите только на две строки за раз.

2) Для каждой строки (v в P (v, i)) вас интересует только i, которое больше увеличивает максимальное значение, которое больше, чем каждый i, который удерживал максимальное значение в предыдущей строке, Кроме того, я = 1, иначе вы никогда не будете рассматривать пробелы.

Ответ 4

Я закодировал его в С++, используя DP в O (nlogk). Идея состоит в том, чтобы поддерживать мультимножество со следующими значениями k для данной позиции. Этот мультимножество обычно имеет значения k в середине обработки. Каждый раз, когда вы перемещаете элемент и нажимаете новый. Искусство заключается в том, как сохранить этот список, чтобы получить прибыль [i] + answer [i + 2]. Подробнее о наборе:

/*
 * Observation 1: ith state depends on next k states i+2....i+2+k
 * We maximize across this states added on them "accumulative" sum
 *
 * Let Say we have list of numbers of state i+1, that is list of {profit + state solution}, How to get states if ith solution
 *
 * Say we have following data k = 3
 *
 * Indices:     0   1   2   3   4
 * Profits:     1   3   2   4   2
 * Solution:    ?   ?   5   3   1
 *
 * Answer for [1] = max(3+3, 5+1, 9+0) = 9
 *
 * Indices:     0   1   2   3   4
 * Profits:     1   3   2   4   2
 * Solution:    ?   9   5   3   1
 *
 * Let find answer for [0], using set of [1].
 *
 * First, last entry should be removed. then we have (3+3, 5+1)
 *
 * Now we should add 1+5, but entries should be incremented with 1
 *      (1+5, 4+3, 6+1) -> then find max.
 *
 *  Could we do it in other way but instead of processing list. Yes, we simply add 1 to all elements
 *
 *  answer is same as: 1 + max(1-1+5, 3+3, 5+1)
 *
 */

ll dp()
{
multiset<ll, greater<ll> > set;

mem[n-1] = profit[n-1];

ll sumSoFar = 0;

lpd(i, n-2, 0)
{
    if(sz(set) == k)
        set.erase(set.find(added[i+k]));

    if(i+2 < n)
    {
        added[i] = mem[i+2] - sumSoFar;
        set.insert(added[i]);
        sumSoFar += profit[i];
    }

    if(n-i <= k)
        mem[i] = profit[i] + mem[i+1];
    else 
        mem[i] = max(mem[i+1], *set.begin()+sumSoFar);
}

return mem[0];
 }

Ответ 5

Это похоже на проблему с линейным программированием. Эта проблема будет линейной, но для требования, чтобы осталось не более смежных рекламных щитов K.

См. википедию для общего лечения: http://en.wikipedia.org/wiki/Linear_programming

Посетите свою университетскую библиотеку, чтобы найти хороший учебник по этому вопросу.

Есть много, много библиотек для помощи в линейном программировании, поэтому я предлагаю вам не пытаться кодировать алгоритм с нуля. Вот список, относящийся к Python: http://wiki.python.org/moin/NumericAndScientific/Libraries

Ответ 6

Пусть P[i] (где я = 1..n) - максимальная прибыль для рекламных щитов 1..i ЕСЛИ МЫ УДАЛИТЬ рекламный щит i. Тривиально рассчитать ответ, зная все P [i]. Базовый алгоритм для вычисления P [i] выглядит следующим образом:

for i=1,N
{
  P[i]=-infinity;
  for j = max(1,i-k-1)..i-1
  {
    P[i] = max( P[i], P[j] + C[j+1]+..+C[i-1] );
  }
}

Теперь идея, которая позволяет нам ускорить процесс. Скажем, у нас есть две разные допустимые конфигурации рекламных щитов 1 через i, позвольте назвать эти конфигурации X1 и X2. Если в конфигурациях X1 и profit(X1) >= profit(X2) удаляется рекламный щит i, тогда мы всегда должны выбирать конфигурацию X1 для рекламных щитов 1..i (profit()). Я имел в виду прибыль только от рекламных щитов 1..i, независимо от конфигурации для i+1..n). Это так же важно, как и очевидно.

Введем двусвязный список кортежей {idx,d}: {{idx1,d1}, {idx2,d2}, ..., {idxN,dN}}.

• p->idx - индекс последнего снятого рекламного щита. p->idx увеличивается по мере прохождения списка: p->idx < p->next->idx
• p->d - это сумма элементов (C[p->idx]+C[p->idx+1]+..+C[p->next->idx-1]), если p не является последним элементом в списке. В противном случае это сумма элементов до текущей позиции минус единица: (C[p->idx]+C[p->idx+1]+..+C[i-1]).

Вот алгоритм:

P[1] = 0;
list.AddToEnd( {idx=0, d=C[0]} );
// sum of elements starting from the index at top of the list
sum = C[0]; // C[list->begin()->idx]+C[list->begin()->idx+1]+...+C[i-1]
for i=2..N
{
  if( i - list->begin()->idx > k + 1 ) // the head of the list is "too far"
  {
    sum = sum - list->begin()->d
    list.RemoveNodeFromBeginning()
  }
  // At this point the list should containt at least the element
  // added on the previous iteration. Calculating P[i].
  P[i] = P[list.begin()->idx] + sum
  // Updating list.end()->d and removing "unnecessary nodes"
  // based on the criterion described above
  list.end()->d = list.end()->d + C[i]
  while(
    (list is not empty) AND
    (P[i] >= P[list.end()->idx] + list.end()->d - C[list.end()->idx]) )
  {
    if( list.size() > 1 )
    {
      list.end()->prev->d += list.end()->d
    }
    list.RemoveNodeFromEnd();
  }
  list.AddToEnd( {idx=i, d=C[i]} );
  sum = sum + C[i]
}

Ответ 7

//shivi..coding is adictive!!
#include<stdio.h>

long long int arr[100001];
long long  int sum[100001];
long long  int including[100001],excluding[100001];
long long int maxim(long long int a,long long int b)
{if(a>b) return a;return b;}

int main()
{
int N,K;
scanf("%d%d",&N,&K);
for(int i=0;i<N;++i)scanf("%lld",&arr[i]);

sum[0]=arr[0];
including[0]=sum[0];
excluding[0]=sum[0];
for(int i=1;i<K;++i)
{
    sum[i]+=sum[i-1]+arr[i];
    including[i]=sum[i];
    excluding[i]=sum[i];
}

long long int maxi=0,temp=0;
for(int i=K;i<N;++i)
{
    sum[i]+=sum[i-1]+arr[i];
    for(int j=1;j<=K;++j)
    {
        temp=sum[i]-sum[i-j];
        if(i-j-1>=0)
        temp+=including[i-j-1];
        if(temp>maxi)maxi=temp;
    }
    including[i]=maxi;
    excluding[i]=including[i-1];
}
printf("%lld",maxim(including[N-1],excluding[N-1]));
}

//here is the code...passing all but 1 test case :) comment improvements...simple DP