Bài này nhìn qua thì thấy rõ ràng muốn AC thì phải có mùi QHĐ trong code, chứ nếu chỉ đệ quy hay Brute-force đảm bảo không AC :)))) Nhưng cách để QHĐ không hề ngắn vì có khá nhiều điều kiện trong bài này (vì mình muốn làm cho bài toán này thực tế hơn chứ không chỉ là trong tưởng tượng), cụ thể như sau:

Nếu gọi \(a[i][j]\) là độ cao của ô \((i; j)\) và \(dp[i][j]\) là đoạn đường ngắn nhất từ ô \((1; 1)\) đến ô \((i; j)\) thì ta có công thức:

• \(i=1\) và \(j=1\): \(dp[i][j]=0\)
• \(i=1\) và \(j>1\): \(dp[i][j]=dp[i][j-1]+\)(hoặc là \(1\cdot(|a[i][j]-a[i][j-1]|+1)\) nếu \(a[i][j]\geq a[i][j-1]\), hoặc là \(1+0.01\cdot(|a[i][j]-a[i][j-1]|)\) nếu ngược lại)
• \(i>1\) và \(j=1\): \(dp[i][j]=dp[i-1][j]+\)(hoặc là \(1\cdot(|a[i][j]-a[i-1][j]|+1)\) nếu \(a[i][j]\geq a[i-1][j]\), hoặc là \(1+0.01\cdot(|a[i][j]-a[i-1][j]|)\) nếu ngược lại)
• \(i>1\) và \(j>1\): \(dp[i][j]=min(\)
  • \(dp[i][j-1]+\)(hoặc là \(1\cdot(|a[i][j]-a[i][j-1]|+1)\) nếu \(a[i][j]\geq a[i][j-1]\), hoặc là \(1+0.01\cdot(|a[i][j]-a[i][j-1]|)\) nếu ngược lại)
  • \(dp[i-1][j]+\)(hoặc là \(1\cdot(|a[i][j]-a[i-1][j]|+1)\) nếu \(a[i][j]\geq a[i-1][j]\), hoặc là \(1+0.01\cdot(|a[i][j]-a[i-1][j]|)\) nếu ngược lại)
  • \(dp[i-1][j-1]+\)(hoặc là \(1\cdot(|a[i][j]-a[i-1][j-1]|+1)\) nếu \(a[i][j]\geq a[i-1][j-1]\), hoặc là \(1+0.01\cdot(|a[i][j]-a[i-1][j-1]|)\) nếu ngược lại)

\()\)

Lúc này các bạn chỉ cần tạo thêm vòng truy hồi lại là được. Chú ý nếu \(dp[n][n]>t\) thì xuất Can't Solve

Nhưng chưa hết, bài này vẫn còn một cái bẫy cực kì quan trọng mà các bạn cần để ý.

“Chơi với cái bàn cờ “kì dị” này riết cũng chán, Tấn đem con Robot nhỏ siêu hiện đại ở nhà ra. Nó hiện đang có 300V trong cái hộp pin siêu cấp của nó và nó cứ mỗi giây chỉ tiêu tốn 0,00001V nếu bật công tắc.”

“Nó hiện đang có 300V trong cái hộp pin siêu cấp của nó và nó cứ mỗi giây chỉ tiêu tốn 0,00001V nếu bật công tắc.”

Và nếu bạn đã để ý, thì bạn đã biết bạn cần phải làm gì rồi đấy :))) Bởi vì nó chỉ chạy được trong vòng \(\frac{300}{0,00001}=30000000s\) thôi (vì sau đó nó sẽ hết pin và không chạy nữa, khúc sau thể nào thời gian cũng vượt \(Ts\) mà thôi) :)))