fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <bitset>
  5. #include <fstream>
  6. #include <string>
  7. #include <string.h>
  8. #include <math.h>
  9. #include <algorithm>
  10. #include <bits/stdc++.h>
  11. #include <sstream>
  12.  
  13. using std::string;
  14. using std::stringstream;
  15. using namespace std;
  16.  
  17. typedef vector<int> vi;
  18. typedef pair<int,int> ii;
  19. typedef vector<ii> vii;
  20.  
  21. typedef unsigned int ui;
  22. typedef unsigned long long llu;
  23. typedef unsigned long lu;
  24. typedef long long ll;
  25.  
  26. #define lakh 100010
  27. #define million 1000010
  28. int inf=1000;
  29. //----------------------------------------------------
  30. int n,reqd[17],given[17],dp[17][1<<17];
  31.  
  32. inline int cost(int row,int i){
  33. return abs(row-i)+abs(reqd[row]-given[i]);
  34. }
  35.  
  36. int solve(int row,int taken){
  37. if(row==n) return 0;
  38. if(dp[row][taken]!=-1) return dp[row][taken];
  39. dp[row][taken]=1000;
  40. for(int i=0;i<n;i++)
  41. if(!(taken & (1<<i)))
  42. dp[row][taken]=min(dp[row][taken],cost(row,i)+solve(row+1,taken|(1<<i)));
  43. return dp[row][taken];
  44. }
  45.  
  46. void display(){
  47. for(int i=0;i<n;i++){
  48. cout<<"\n"<<i<<": ";
  49. for(int j=0;j<2;j++)
  50. cout<<dp[i][j]<<" ";
  51. }
  52. }
  53.  
  54. int main(){
  55. cin>>n;
  56. while(n!=0){
  57. memset(dp,-1,sizeof(dp));
  58. for(int i=0;i<n;i++) cin>>given[i];
  59. for(int i=0;i<n;i++) cin>>reqd[i];
  60. cout<<solve(0,0)<<endl;
  61. //display();
  62. cin>>n;
  63. }
  64. return 0;
  65. }
  66.  
  67.  
Success #stdin #stdout 0s 24768KB
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