fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <cassert>
  4. #include <map>
  5. #include <algorithm>
  6. #include <cmath>
  7. using namespace std;
  8.  
  9. #define INF (1<<30)
  10.  
  11. class AC_Solution{
  12. public:
  13. 	struct NODE{
  14. 		int x,cost;
  15. 		NODE(int x,int cost) : x(x) , cost(cost) {}
  16. 		bool operator < (const NODE &a) const{
  17. 			return cost > a.cost;
  18. 		}
  19. 	};
  20. 	int getDistance(int a,int b){
  21. 		return abs(a-b) == 1 ? 2 : (abs(a-b)+2) / 3; 
  22. 	}
  23.  
  24. 	int getCost(int a,int b){
  25. 		priority_queue<NODE> Q;
  26. 		Q.push(NODE(b,0));
  27. 		map<int,bool> used;
  28. 		while(Q.size()){
  29. 			NODE q = Q.top(); Q.pop();
  30. 			assert(q.x >= 0);
  31. 			if(used[q.x])continue;
  32. 			else used[q.x] = true;
  33. 			if(q.x==a) return q.cost;
  34. 			int sq = sqrt(q.x);
  35. 			if(sq != 0)Q.push( NODE( (sq-1) , q.cost + 1 + getDistance(q.x,(sq-1)*(sq-1)) ) );
  36. 			Q.push( NODE( sq , q.cost + 1 + getDistance(q.x,sq*sq) ) );
  37. 			Q.push( NODE( (sq+1) , q.cost + 1 + getDistance(q.x,(sq+1)*(sq+1)) ) );
  38. 			Q.push( NODE( a , q.cost + getDistance(q.x , a) ) );
  39. 		}
  40. 		assert(0);
  41. 		return -1;
  42. 	}
  43.  
  44. 	int solve(vector<int> fav){
  45. 		static int dp[1<<11][11];
  46. 		int graph[11][11]={} , N = fav.size();
  47. 		for(int i = 0 ; i < (1<<N) ; i++)
  48. 			for(int j = 0 ; j < N ; j++)
  49. 				dp[i][j] = INF;
  50.  
  51. 		for(int i = 0 ; i < N ; i++){
  52. 			for(int j = 0 ; j < N ; j++){
  53. 				graph[i][j] = getCost(fav[i],fav[j]);
  54. 			}
  55. 		}
  56. 		for(int i = 0 ; i < N ; i++) dp[1<<i][i] = 0;
  57.  
  58. 		for(int i = 0 ; i < (1<<N) ; i++)
  59. 			for(int j = 0 ; j < N ; j++)
  60. 				for(int k = 0 ; k < N ; k++)
  61. 					dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k],dp[i][j]+graph[j][k]);
  62. 		int ans = INF;
  63. 		for(int i = 0 ; i < N ; i++) ans = min( ans , dp[(1<<N)-1][i] );
  64. 		return ans;
  65. 	}
  66. };
  67.  
  68. int main(){
  69. 	int n;
  70. 	cin >> n;
  71. 	vector<int> fav;
  72. 	for(int i = 0 ; i < n ; i++){int t; cin >> t; fav.push_back(t); }
  73. 	cout << AC_Solution().solve(fav) << endl;
  74.  
  75. }
Success #stdin #stdout 0.02s 2824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1073741824
https://ideone.com/BzrWj
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!