Advertisement
Guest User

Untitled

a guest
Nov 24th, 2014
178
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.26 KB | None | 0 0
  1. #include <bits\stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define mp make_pair
  5. typedef long double ld;
  6. typedef long long ll;
  7. typedef unsigned long long ull;
  8.  
  9. const ld eps = 1e-9;
  10. const int inf = 1e9;
  11. inline ld dist(int l, int r, const vector<ld> &x, const vector<ld> &y)
  12. {
  13. return sqrt((x[l] - x[r]) * (x[l] - x[r]) + (y[l] - y[r]) * (y[l] - y[r]));
  14. }
  15.  
  16. void solve(int n)
  17. {
  18. int tail, hand, foot, body;
  19. int ktail, khand, kfoot;
  20.  
  21. hand = n;
  22. cin >> body >> foot >> tail;
  23. cin >> khand >> kfoot >> ktail;
  24.  
  25. cin >> n;
  26. vector<ld> x(n), y(n);
  27. double temp;
  28.  
  29. for (int i = 0; i < n; i++)
  30. {
  31. scanf(" %lf", &temp); x[i] = temp;
  32. scanf(" %lf", &temp); y[i] = temp;
  33. }
  34.  
  35. int dp[khand + 1][kfoot + 1][ktail + 1][n][3];
  36. for (int i = 0; i <= khand; i++)
  37. for (int j = 0; j <= kfoot; j++)
  38. for (int k = 0; k <= ktail; k++)
  39. for (int pos = 0; pos < n; pos++)
  40. for (int wtf = 0; wtf < 3; wtf++)
  41. dp[i][j][k][pos][wtf] = inf;
  42.  
  43. if (khand >= 1)
  44. dp[1][0][0][0][0] = 0;
  45. if (kfoot >= 1)
  46. dp[0][1][0][0][1] = 0;
  47. if (ktail >= 1)
  48. dp[0][0][1][0][2] = 0;
  49.  
  50. for (int len = 1; len <= n; len++)
  51. for (int i = 0; i <= khand; i++)
  52. for (int j = 0; j <= kfoot; j++)
  53. for (int k = 0; k <= ktail; k++)
  54. for (int start = 0; start < n; start++)
  55. for (int where = 0; where < 3; where++)
  56. for (int to = 0; to < 3; to++)
  57. for (int dest = 0; dest < n; dest++)
  58. if (dp[i][j][k][start][where] < inf)
  59. {
  60. if (where == 2 && to == 2)
  61. continue;
  62.  
  63. ld reallen = dist(start, dest, x, y);
  64. ll pathlen = body;
  65. if (where == 0)
  66. pathlen += hand;
  67. else if (where == 1)
  68. pathlen += foot;
  69. else if (where == 2)
  70. pathlen += tail;
  71. if (to == 0)
  72. pathlen += hand;
  73. else if (to == 1)
  74. pathlen += foot;
  75. else if (to == 2)
  76. pathlen += tail;
  77.  
  78. if (pathlen + eps >= reallen)
  79. {
  80. bool ok = false;
  81. ok |= (i < khand && to == 0);
  82. ok |= (j < kfoot && to == 1);
  83. ok |= (k < ktail && to == 2);
  84. if (!ok)
  85. continue;
  86.  
  87. int ni = i;
  88. int nj = j;
  89. int nk = k;
  90. if (to == 0)
  91. ni++;
  92. if (to == 1)
  93. nj++;
  94. if (to == 2)
  95. nk++;
  96.  
  97. int &reef = dp[ni][nj][nk][dest][to];
  98. if (reef > dp[i][j][k][start][where] + 1)
  99. reef = dp[i][j][k][start][where] + 1;
  100. }
  101. }
  102.  
  103. int ans = inf;
  104.  
  105. for (int i = 0; i <= khand; i++)
  106. for (int j = 0; j <= kfoot; j++)
  107. for (int k = 0; k <= ktail; k++)
  108. for (int where = 0; where < 3; where++)
  109. ans = min(ans, dp[i][j][k][n - 1][where]);
  110.  
  111. if (ans == inf)
  112. printf("-1\n");
  113. else
  114. printf("%d\n", ans + 1);
  115. }
  116.  
  117. int main()
  118. {
  119. #ifndef ONLINE_JUDGE
  120. // freopen("input.txt", "rt", stdin);
  121. // freopen("output.txt", "w", stdout);
  122. #endif // ONLINE_JUDGE
  123. freopen("tote.in", "rt", stdin);
  124. freopen("tote.out", "w", stdout);
  125.  
  126. int n;
  127. while (cin >> n)
  128. solve(n);
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement