Cố Trường Ca
Senior Member
K bạn, cứ feed thoải mái đi
thảo luận Leetcode mỗi ngày
- Người tạo chủ đề _Gia_Cat_Luong_
- Ngày bắt đầu
- Trạng thái
freedom.9
Senior Member
aNotHeRNo0b
Senior Member
anoldvozer1710.v2
Senior Member
vl cuối tháng gặp ngay cái bài Hard dài như cái sớ vậy 
LmaoSuVuong
Senior Member
chưa ai làm luôn chứ ko phải ítBài hôm nay ít người làm thế nhỉ
freedom.9
Senior Member
Nghĩ là có cách greedy nhưng mà constrain thấp quá nên làm DP cũng pass 
ăn 1 bug do ko nghĩ là capacity của nhà máy cũng = 0 nữa
Ồ cách flatten cái capacity của factory hay phết, đỡ phải lưu thêm 1 state trong DP function nhưng time complexity là như nhau
ăn 1 bug do ko nghĩ là capacity của nhà máy cũng = 0 nữa
Python:
class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
robot = sorted(robot)
n = len(robot)
factory = sorted(factory)
m = len(factory)
@lru_cache(None)
def go(i, j, capacity):
if i == n:
return 0
if j == m:
return inf
skip = go(i, j + 1, factory[j + 1][1] if j + 1 < m else 0)
take = inf
if capacity > 0:
take = abs(robot[i] - factory[j][0]) + go(i + 1, j, capacity - 1)
return min(skip, take)
return go(0, 0, factory[0][1])Ồ cách flatten cái capacity của factory hay phết, đỡ phải lưu thêm 1 state trong DP function nhưng time complexity là như nhau
anoldvozer1710.v2
Senior Member
freedom.9
Senior Member
vanphuoc1029
Senior Member
Bài hôm nay khó ác, cũng nghĩ là dp nhưng không biết xử lý cái limit ra sao. Đành phải vào solution thì mới biết nó dup cái position bằng với limit trong factory pos array luôn, hay phết.
alone_wolf
Senior Member
C++:
class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
sort(robot.begin(), robot.end());
sort(factory.begin(), factory.end());
vector<vector<vector<long long>>> dp(
robot.size(),
vector<vector<long long>>(
factory.size(),
vector<long long>(robot.size() + 1, -1)
)
);
return f(robot, factory, 0, 0, 0, dp);
}
long long f(vector<int>& robot, vector<vector<int>>& factory, int i, int j, int used, vector<vector<vector<long long>>>& dp) {
if (j == factory.size()) return LLONG_MAX / 2;
if (i == robot.size()) return 0;
if (dp[i][j][used] != -1) return dp[i][j][used];
long long not_take = f(robot, factory, i, j + 1, 0, dp);
long long take_current = LONG_MAX;
if (used < factory[j][1]) {
take_current = f(robot, factory, i + 1, j, used + 1, dp) + abs(1LL * robot[i] - factory[j][0]);
} else {
take_current = f(robot, factory, i, j + 1, 0, dp);
}
return dp[i][j][used] = min(take_current, not_take);
}
};freedom.9
Senior Member
Giả sử có 4 điểm, 2 con robot ở A B và 2 điểm C D tạo thành 1 hình chữ nhật A B C D thì tổng độ dài 2 đường chéo luôn lớn hơn tổng độ dài 2 cạnh bên mà. Nên việc cần làm là cần tránh tình trạng giao nhau giữa các đường di chuyển của robot. Nên việc sorting sẽ chắc chắn optimal.bài hôm nay khó ở đoạn chứng minh ban đầu là sorting works
Lúc đầu mình nghĩ tới 2 pointers, nhưng mà 2 pointers thì sẽ ko có cách nào chọn cái factory cho optimal cả nên DP sẽ ăn. Nhìn constrain thấp nên dùng DP ăn cũng dễ hiểu
via theNEXTvoz for iPhone
Rõ rồi sếp
Mà sếp gạch em vừa chứ nick em vẫn Junior mà ăn gạch mãi thế sao lớn nổi
freedom.9
Senior Member
Đi Spam ăn gạch là đúngRõ rồi sếp
Mà sếp gạch em vừa chứ nick em vẫn Junior mà ăn gạch mãi thế sao lớn nổi
via theNEXTvoz for iPhone
anoldvozer1710.v2
Senior Member
như @Cố Trường Ca huynh còn âm hơn Nam Cực mà còn coi nhẹ tựa lông hồng thì fency vẫn còn ấm lắmRõ rồi sếp
Mà sếp gạch em vừa chứ nick em vẫn Junior mà ăn gạch mãi thế sao lớn nổi
freedom.9
Senior Member
dùng lru vẫn MLE sếp ạ, méo hiểu, chắc phải qua tabulation
- Trạng thái
Chủ đề tương tự
