Создание максимальной длины восходящего подмассива из массива всего с 3 допустимыми ходами - PullRequest
Новая
       28

Создание максимальной длины восходящего подмассива из массива всего с 3 допустимыми ходами

3 голосов
/ 14 апреля 2019

Мне нужно решить эту проблему с помощью DP, и вот проблема: у нас есть массив, и мы хотим создать восходящий подмассив с максимальным размером с 2 условиями:

  1. Мы можем просто пройтимассив один раз слева направо.
  2. У нас есть только два допустимых хода для создания этого подмассива:
    • Мы можем игнорировать следующий элемент в массиве в обходе
    • Мы можем поместить следующий элемент в конец или начало массива, и этот массив должен быть в порядке возрастания

для .eg:

input: arr[ ] = {0 , 3 , 10 , 7 , 6 , 5 , 14}

вывод: 5

, а вспомогательный массив - {5 , 6, , 7 , 10 , 14}

. Решение для этого экземпляра - начать с 10, а затем поставить 7 слеваи 6 и 5 слева, затем поставьте 14 справа от 10

Это означает, что мы можем расширить массив на эти условия слева и справа

1 Ответ

2 голосов
/ 14 апреля 2019

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

давайте определим наше состояние dp [c] [dec] [inc] - теперь мы смотрим на элемент в позиции c, элемент в конце построенной нами последовательности находится в позиции dec, а элемент в начале последовательность в положении вкл.

Итак, теперь мы можем перейти к:

  • dp [c + 1] [dec] [inc] путем пропуска текущего элемента
  • dp [c + 1] [c] [inc], поместив текущий элемент на оборотную сторону (действует только если a [c] <= a [dec]) </li>
  • dp [c + 1] [dec] [c], поместив текущий лемент спереди (действует только если a [c]> = a [inc])

пример кода (C ++): 

const int n = 7;
int a[] = {0, 0, 3, 10, 7, 6, 5, 14};
int dp[n+1][n+1][n+1];

int solve(int c, int dec, int inc)
{
    if(c > n)return 0;
    if(dp[c][dec][inc] != -1)return dp[c][dec][inc];

    dp[c][dec][inc] = solve(c+1,dec,inc); //skip element
    if(inc==0 && dec==0) //if our sequence is empty, try appending element to sequence
        dp[c][dec][inc] = max(dp[c][dec][inc], 1 + solve(c+1,c,c));
    else if(a[c] >= a[inc])//we can extend our array [dec, ..., inc] because current element can be put to front
        dp[c][dec][inc] = max(dp[c][dec][inc], 1 + solve(c+1,dec,c));
    else if(a[c] <= a[dec])//we can extend our array [dec, ..., inc] because current element can be put to back
        dp[c][dec][inc] = max(dp[c][dec][inc], 1 + solve(c+1,c,inc));

    return dp[c][dec][inc];
}

int main()
{
    memset(dp, -1, sizeof dp);
    cout<<solve(1,0,0);
}

Сложность O (n ^ 3)

...