Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

yawn_lento's blog

By yawn_lento, history, 4 months ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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