fork(1) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int M = 32;
  5. int n;
  6. int x[16]; // x[i] in 1 .. M
  7. int y[16];
  8.  
  9. int F[M+1];
  10. int f(int x){return F[x] == x ? x : F[x] = f(F[x]);}
  11. bool important[M+1];
  12. int flux[M+1]; // from i to i+1
  13.  
  14. void merge(int a, int b)
  15. {
  16. int fa = f(a), fb = f(b);
  17. if(fa != fb)
  18. F[fa] = fb;
  19. }
  20.  
  21. struct edge
  22. {
  23. int a, b, len;
  24. bool operator <(const edge that)const
  25. {
  26. return len < that.len;
  27. }
  28. };
  29.  
  30. int solve()
  31. {
  32. for(int i = 1; i <= M; i++)
  33. F[i] = i;
  34. memset(flux, 0, sizeof(flux));
  35. memset(important, false, sizeof(important));
  36. for(int i = 0; i < n; i++)
  37. {
  38. merge(x[i], y[i]);
  39. important[x[i]] = important[y[i]] = true;
  40.  
  41. if(x[i] < y[i])
  42. for(int j = x[i]; j < y[i]; j++)
  43. flux[j] ++;
  44. if(x[i] > y[i])
  45. for(int j = y[i]; j < x[i]; j++)
  46. flux[j] --;
  47. }
  48. int ans = 0;
  49. for(int i = 1; i < M; i++)
  50. {
  51. if(flux[i] < 1)
  52. merge(i, i+1);
  53. if(flux[i] > 1)
  54. {
  55. ans += flux[i] - 1;
  56. merge(i, i+1);
  57. }
  58. }
  59. vector <edge> lis;
  60. int prevImportant = -1;
  61. for(int i = 1; i <= M; i++)
  62. if(important[i])
  63. {
  64. if(prevImportant != -1)
  65. {
  66. if(f(prevImportant) != f(i))
  67. {
  68. edge e;
  69. e.a = prevImportant;
  70. e.b = i;
  71. e.len = i - prevImportant;
  72. lis.push_back(e);
  73. }
  74. }
  75. prevImportant = i;
  76. }
  77. sort(lis.begin(), lis.end());
  78. for(int i = 0; i < lis.size(); i++)
  79. {
  80. if(f(lis[i].a) != f(lis[i].b))
  81. {
  82. ans += lis[i].len;
  83. merge(lis[i].a, lis[i].b);
  84. }
  85. }
  86. return ans;
  87. }
  88.  
  89. int dp[1<<16][16];
  90.  
  91. int dodp(int mask, int last)
  92. {
  93. if(mask == (1<<n)-1) return 0;
  94. int &ret = dp[mask][last];
  95. if(ret != -1) return ret;
  96. ret = 1000000000;
  97. for(int i = 0; i < n; i++)
  98. if((mask & (1<<i)) == 0)
  99. ret = min(ret, dodp(mask | (1<<i) , i) + max(0, y[last] - x[i]));
  100. return ret;
  101. }
  102.  
  103. int bruteforce()
  104. {
  105. memset(dp, 0xff, sizeof(dp));
  106. int ret = 1000000000;
  107. for(int i = 0; i < n; i++)
  108. ret = min(ret, dodp(1<<i, i));
  109. return ret;
  110. }
  111.  
  112. int MAIN()
  113. {
  114. srand((unsigned)time(NULL));
  115. int nCorrect = 0;
  116. for(int testCase = 1; testCase <= 500; testCase ++)
  117. {
  118. /*cin >> n;
  119. for(int i = 0; i < n; i++)
  120. cin >> x[i];
  121. for(int i = 0; i < n; i++)
  122. cin >> y[i];*/
  123. n = rand() % 16 + 1;
  124. for(int i = 0; i < n; i++)
  125. {
  126. x[i] = rand() % 32 + 1;
  127. y[i] = rand() % 32 + 1;
  128. }
  129. int ansBF = bruteforce();
  130. int ans = solve();
  131. if(ansBF != ans) cout << "ERROR" << endl;
  132. else nCorrect ++;
  133. }
  134. cout << nCorrect << " correct " << endl;
  135. return 0;
  136. }
  137.  
  138. int main()
  139. {
  140. int start = clock();
  141. #ifdef LOCAL_TEST
  142. freopen("in.txt", "r", stdin);
  143. freopen("out.txt", "w", stdout);
  144. #endif
  145. ios :: sync_with_stdio(false);
  146. cout << fixed << setprecision(16);
  147. int ret = MAIN();
  148. #ifdef LOCAL_TEST
  149. cout << "[Finished in " << clock() - start << " ms]" << endl;
  150. #endif
  151. return ret;
  152. }
  153.  
Success #stdin #stdout 2.34s 7564KB
stdin
Standard input is empty
stdout
500 correct