Пожалуйста, подпишитесь на официальный канал 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
  • Проголосовать: не нравится

»
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 месяца назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

since N is so small can't you check all paths

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

    course we can,like DFS,but just trying to offer a different perspective where Mathematical thinking and methods become less significant,praying on randomlized approaches to be equal to the answers given by DP, kind of more interesting