fork(1) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int inf = 1005;
  5. int n,dp[1<<18][18],baby[18],me[18];
  6. int solve(int mask, int k){
  7. if(dp[mask][k]!=-1)return dp[mask][k];
  8. if(k==0)return 0;
  9. int ans = inf;
  10. for(int i=1; i<=n; i++){
  11. if(mask & (1<<i)){
  12. ans = min(ans, abs(i-k) + abs(me[i]-baby[k]) + solve(mask&(~(1<<i)), k-1));//remove this bit ie one less baby row and than number of way for k-1 rows...
  13. }
  14. }
  15. return dp[mask][k] = ans;
  16. }
  17.  
  18. int main(){
  19. while(scanf("%d",&n)){
  20. if(n==0)break;
  21. memset(dp, -1, sizeof dp);
  22. for(int i=1; i<=n; i++)scanf("%d",&baby[i]);
  23. for(int i=1; i<=n; i++)scanf("%d",&me[i]);
  24. cout<<solve((1<<n+1) -1, n)<<endl;
  25. }
  26. return 0;
  27. }
  28.  
Success #stdin #stdout 0s 34496KB
stdin
4 
1 2 3 4 
3 1 4 2 
4 
3 2 4 1 
3 1 4 2 
5 
5 3 1 4 2 
5 3 1 4 2 
5 
1 5 2 4 3 
3 1 4 2 5 
0
stdout
6
2
0
8