levi.ackerman1732's blog

By levi.ackerman1732, history, 7 weeks ago, In English

Problem: 1272D - Remove One Element

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.

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by levi.ackerman1732 (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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])$$$