Hướng dẫn cho Ma trận lên và xuống
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
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.”
Các bạn ai cũng đọc được câu này (nếu chăm). Nhưng liệu các bạn có để ý đến 1 sự sắp đặt kì lạ trong câu in đậm này không?
“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) :)))
Bình luận