Блог пользователя Roach00

Автор Roach00, история, 5 лет назад, По-английски

This is the problem https://codeforces.com/contest/977/problem/F

These are the two solutions :

https://codeforces.com/contest/977/submission/55982217 (correct one)

https://codeforces.com/contest/977/submission/55982195 (wrong one)

The one line change is during input taking iteration where I am assigning value to dp[a[i]]. first I assigned dp[a[i]] = 1 , which gave wrong answer at large input(so can't debug by myself) but then when I changed it to dp[a[i]] = 0 , it made the solution accepted , but if you will see just next interation after the input taking iteration , it doesn't make sense to me because dp[a[i]] = max(dp[a[i]] , dp[a[i] — 1] + 1) should take care of the dp[a[i]] = 1. I don't know am I missing something?

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

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

Try test: 3 2 1 2

And look on this line "dp[a[i]] = max(dp[a[i]] , dp[a[i] — 1] + 1);" when i = 0.