Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Блог пользователя levi.ackerman1732

Looking for flaw in my solution for Round #605(Div. 3D)
Автор levi.ackerman1732, история, 3 года назад, По-английски

Problem: 1272D - Удалите один элемент

My Solution:108781615

Hello all,

My idea: if two elements are in strictly increasing order(i.e a[I] < a[I+1] ) dp[I+1] = dp[I] + 1

else check if a[I-1] < a[I+1] then dp[I+1] = dp[I-1] + 1

I am not sure where this is going wrong. Any help is appreciated. Thanks for your time.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

You should also save another state to indicate whether you have already used up your ability to delete an element or not. Something like:

$$$dp[i+1][b]=dp[i][b]+1$$$, for $$$b\in \{0,1\}$$$, if $$$a[i]<a[i+1]$$$

$$$dp[i+1][1]=dp[i-1][0]+1$$$, if $$$a[i-1]<a[i+1]$$$

return $$$max(dp[n][0],dp[n][1])$$$

→ Ответить