Advertisement
Guest User

Untitled

a guest
Apr 30th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int dp[(1 << 20) + 7];
  6. int pos[27][2];
  7. int main()
  8. {
  9. int n;
  10. cin >> n;
  11. for (int j = 0; j < 2; j++)
  12. {
  13. for (int i = 1; i <= n; i++)
  14. {
  15. int x;
  16. cin >> x;
  17. pos[x][j] = i;
  18. }
  19. }
  20. for (int mask = 0; mask < (1 << n); mask++)
  21. {
  22. int bitCnt = 0;
  23. for (int i = 0; i < n; i++)
  24. {
  25. if (mask & (1 << i)) bitCnt++;
  26. }
  27. int any = 0;
  28. for (int i = 0; i < n; i++)
  29. {
  30. if (mask & (1 << i))
  31. {
  32. dp[mask] = i;
  33. any = i;
  34. }
  35. }
  36. if (bitCnt == 1)
  37. {
  38. dp[mask] = any + 1;
  39. }
  40. else
  41. {
  42. int p = 0;
  43. if (bitCnt % 2 != n % 2) p = 1;
  44. dp[mask] = dp[mask ^ (1 << any)];
  45. for (int i = 0; i < n; i++)
  46. {
  47. if (mask & (1 << i))
  48. {
  49. if (pos[dp[mask ^ (1 << i)]][p] < pos[dp[mask]][p])
  50. {
  51. dp[mask] = dp[mask ^ (1 << i)];
  52. }
  53. }
  54. }
  55. }
  56. }
  57. printf("%d\n", dp[(1 << n) - 1]);
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement