classSolution{public:longlongminimumTotalDistance(vector<int>&robot,vector<vector<int>>&factory){ranges::sort(robot);ranges::sort(factory);vector<vector<vector<long>>>mem(robot.size(),vector<vector<long>>(factory.size(),vector<long>(robot.size())));returnminimumTotalDistance(robot,factory,0,0,0,mem);}private:// Returns the minimum distance to fix robot[i..n) with factory[j..n), where// factory[j] already fixed k robots.longminimumTotalDistance(constvector<int>&robot,constvector<vector<int>>&factory,inti,intj,intk,vector<vector<vector<long>>>&mem){if(i==robot.size())return0;if(j==factory.size())returnLONG_MAX;if(mem[i][j][k]>0)returnmem[i][j][k];constlongskipFactory=minimumTotalDistance(robot,factory,i,j+1,0,mem);constintposition=factory[j][0];constintlimit=factory[j][1];constlonguseFactory=limit>k?minimumTotalDistance(robot,factory,i+1,j,k+1,mem)+abs(robot[i]-position):LONG_MAX/2;returnmem[i][j][k]=min(skipFactory,useFactory);}};
classSolution:defminimumTotalDistance(self,robot:list[int],factory:list[list[int]],)->int:robot.sort()factory.sort()@functools.lru_cache(None)defdp(i:int,j:int,k:int)->int:""" Returns the minimum distance to fix robot[i..n) with factory[j..n), where factory[j] already fixed k robots. """ifi==len(robot):return0ifj==len(factory):returnmath.infskipFactory=dp(i,j+1,0)position,limit=factory[j]useFactory=(dp(i+1,j,k+1)+abs(robot[i]-position)iflimit>kelsemath.inf)returnmin(skipFactory,useFactory)returndp(0,0,0)
Thanks for stopping by! If you find this site helpful, consider buying me some protein powder to keep me fueled! π