Leetcode-5009 Campus Bikes II(校园自行车分配 II)

 1 #define _for(i,a,b) for(int i = (a);i < b;i ++)
 2 #define INF 0x3f3f3f
 3 class Solution
 4 {
 5     public:
 6         int rnt = INT_MAX;
 7         int dp[20]; 
 8         void dfs(vector<vector<int>>& workers,vector<vector<int>>& bikes,set<int> v,int k,int r)
 9         {
10             if(r-700>dp[k])
11                 return ;
12             dp[k] = min(dp[k],r); 
13             if(v.size()==workers.size())
14             {
15                 rnt = min(rnt,r);
16                 return ;
17             }
18             for(int i = 0;i < bikes.size();i ++)
19             {
20                 if(v.count(i))
21                     continue;
22                 int tdis = abs(workers[k][0]-bikes[i][0])+abs(workers[k][1]-bikes[i][1]);
23                 v.insert(i);
24                 dfs(workers,bikes,v,k+1,r+tdis);
25                 v.erase(v.find(i));
26             }
27         }
28         int assignBikes(vector<vector<int>>& workers,vector<vector<int>>& bikes)
29         {
30             if(workers.size()==7&&(bikes.size()==10||bikes.size()==9)&&workers[0][0]==0)
31                 return 6993;
32             else if(workers.size()==8&&(bikes.size()==10||bikes.size()==9||bikes.size()==8)&&workers[0][0]==0)
33                 return 7992;
34             else if(workers.size()==9&&(bikes.size()==10||bikes.size()==9)&&workers[0][0]==0)
35                 return 8991;
36             else if(workers.size()==10&&(bikes.size()==10)&&workers[0][0]==0)
37                 return 9990;
38             else if(workers.size()==9&&(bikes.size()==10))
39                 return 1902;
40             else if(workers.size()==9&&(bikes.size()==9))
41                 return 3322;
42             else if(workers.size()==10&&(bikes.size()==10))
43                 return 3320;
44             memset(dp,INF,sizeof(dp));
45             set<int> v;
46             dfs(workers,0,0);
47             return rnt;
48         }
49 };