I was read a solution of problem at here. But i don't know why minus dp[l+1][r] if first people choose a[l] and dp[l][r-1] if first people choose a[r]. Can else help me, thanks :>>

# | User | Rating |
---|---|---|

1 | tourist | 3690 |

2 | jiangly | 3647 |

3 | Benq | 3581 |

4 | orzdevinwang | 3570 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | Radewoosh | 3509 |

8 | ecnerwala | 3486 |

9 | jqdai0815 | 3474 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | awoo | 164 |

3 | adamant | 163 |

4 | TheScrasse | 159 |

5 | nor | 157 |

6 | maroonrk | 155 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

8 | orz | 146 |

10 | BledDest | 145 |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2024 22:38:08 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I got an AC score for a problem. I wrote something that can help you.

For example, if the first person chooses a[l], the subsequence a seq [l+1..r] will be chosen by the second person. This is because both individuals are optimizing their scores. So, I will swap the positions of the second person with the second position of the first person and calculate

I think you need to understand it properly.

`dp[l][r]`

= $$$score_1-score_2$$$ if the game played only on interval`[l, r]`

.Now note 2 things: $$$score_1$$$ is score of $$$player_1$$$ and $$$score2$$$ is score of $$$player_2$$$ and on each move, $$$player_1$$$ and $$$player_2$$$ are alternating.

Let's say $$$A$$$ is $$$player_1$$$ and $$$B$$$ is $$$player_2$$$ on segment

`[l,r]`

. $$$A$$$ chooses`x[l]`

. Now in segment`[l+1,r]`

, $$$B$$$ will be the $$$player_1$$$. This is how it becomes a dynamic programming problem. The output of smaller subsegments don't change no matter what and they help build outputs for bigger subsegments. Note that $$$A$$$ and $$$B$$$ will always be $$$player_1$$$ on the same subsegments no matter which numbers are removed first.In short:

`[l,r]`

, then`dp[l][r]`

will store`scoreA-scoreB`

.`[l+1,r]`

then`dp[l+1][r]`

will store`scoreB-scoreA`

,`[l,r-1]`

then`dp[l][r-1]`

will store`scoreB-scoreA`

.I hope that makes sense why

`dp[l][r] = max(x[l] - dp[l+1][r] , x[r] - dp[l][r-1])`

hey . could you explain why cant we take a greedy approach on the problem? specifically what i thought was for every turn calculate sum of odd and even indexed terms left in sequence and choose left or right end accordingly. for example, if i see 4 5 1 3 as vector , i take left at 4 and right at 3 inititally now player one calculates sum of even positions -> 4 + 1=5 , and odd positions-> 5+3=8. so he goes with 3 as first choice ,next second player does the same(as both play optimally) and he goes with 4 . the player 1 ends with 5 making his total 5+3. However this strategy fails in many cases and i am unable to figure out why. please help

What does your solution do when number of positions is odd? In that case, left and right indexes both would be at even position, so how do you know what to choose then?

what does optimally means in all these type of questions ?

One way to think about it is to think recursively.

If it's

`A`

's turn, he will check every possibility and make the move that gives him best chances in the worst case scenario. And,`B`

will do the same.