Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Автор yawn_lento, история, 4 месяца назад, По-английски

My attemt using Monte Carlo, effective when the number is small, but will resulting in WA when dealing with larger numbers.The advantage lies in its simplicity in maths logic, while the disadvantage leadsto repetitive attemps in same paths;

You can view the full, well-formatted C++ source code of Monte Carlo method here on GitHub:

https://github.com/yawn-lento/yawn-s-codes/blob/main/P10002-Monte%20Carlo.cpp

As for DFS, using iteration and recursion does make a crucial difference: we no longer waste our time on same paths, instead memory mechanism is introduced(though still not very effective). However, we still have to try every single paths when the number grows exponentially, ending up in TLE.

You can view the full, well-formatted C++ source code of DFS method here on GitHub:

https://github.com/yawn-lento/yawn-s-codes/blob/main/P1002-DFS%E5%B0%9D%E8%AF%95.cpp

Finally we come to the DP method. Focusing only on results using iteration and recursion, the calculation complicity is dramatically reduced, with the only cost of not knowing the exactly how a specific path looks like.

You can view the full, well-formatted C++ source code of DP method here on GitHub:

https://github.com/yawn-lento/yawn-s-codes/blob/main/P1002-DP.cpp

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

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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