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

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

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

Title: Grid Access (NOIP 2000) Problem Description: There is an N×N grid (N≤9). Some cells contain positive integers, while others contain 0.

A person starts from the top-left cell A and walks to the bottom-right cell B. He can only move downward or rightward during the walk.

When he passes through a cell, he takes the number in that cell (the number becomes 0 after being taken).

Now, this person needs to walk from A to B twice. Find the maximum possible sum of the numbers taken from the two paths.

Input Format: The first line contains a single integer N, representing the size of the grid. The following lines contain triples of integers x,y,v, where v is the integer placed in the cell at row x and column y.

The input is terminated by a single line containing 0 0 0.

Output Format: Output a single integer, representing the maximum total sum of the numbers collected on the two paths.

Sample Input:

8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0

Sample Output:

67

Constraints:

1≤N≤9,1≤x,y≤N,1≤v≤30

Using two layer of Monte Carlo and Greey algorithm, I managed to gain AC, though still achievable at small numbers.

below are my codes in Github:

https://github.com/yawn-lento/yawn-s-codes/blob/main/P1004%20%E5%8F%8C%E5%B1%82%E9%9A%8F%E6%9C%BA%E5%B5%8C%E5%A5%97%E5%B0%9D%E8%AF%95.cpp

Полный текст и комментарии »

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

Автор 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
  • Проголосовать: не нравится