Advertisement
antonis47

Untitled

Sep 19th, 2019
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.34 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. typedef long double ld;
  6. typedef pair <int, int> pii;
  7. typedef tuple<int, int, int> tiii;
  8. typedef tuple<int, int, int, int> tiiii;
  9. #define F(i, a, b) for(int i = a; i <= (int)b; i++)
  10. #define f(i, a, b) for(int i = a; i >= (int)b; i--)
  11. #define wh(n) int iteration = n; while(iteration--)
  12. #define For(t, it) for(auto it = (t).begin(); it != (t).end(); ++it)
  13. #define IN insert
  14. #define PB push_back
  15. #define MP make_pair
  16. #define MT make_tuple
  17.  
  18. int main(){
  19. ios_base::sync_with_stdio(false);
  20. cin.tie(NULL);
  21. #ifdef LOCAL
  22. freopen("input.txt", "r", stdin);
  23. freopen("output.txt", "w", stdout);
  24. #endif
  25. int q;
  26. cin >> q;
  27. wh(q){
  28. ll n, a, b;
  29. cin >> n;
  30. ll dp[n][3];
  31. ll ls0, ls1, ls2;
  32. F(i, 0, n-1){
  33. cin >> a >> b;
  34. if(!i){
  35. ls0 = a;
  36. ls1 = a+1;
  37. ls2 = a+2;
  38. dp[i][0] = 0;
  39. dp[i][1] = b;
  40. dp[i][2] = 2*b;
  41. }else{
  42. bool done = 0;
  43. if(ls0 == a && !done){
  44. dp[i][0] = min(dp[i-1][1], dp[i-1][2]);
  45. dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + b;
  46. dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + 2*b;
  47. done = 1;
  48. }
  49. if(ls0 == a+1 && !done){
  50. dp[i][0] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
  51. dp[i][1] = min(dp[i-1][1], dp[i-1][2]) + b;
  52. dp[i][2] = min(dp[i-1][0], dp[i-1][2]) + 2*b;
  53. done = 1;
  54. }
  55. if(ls0 == a+2 && !done){
  56. dp[i][0] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
  57. dp[i][1] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) + b;
  58. dp[i][2] = min(dp[i-1][2], dp[i-1][1]) + 2*b;
  59. }
  60. if(ls1 == a && !done){
  61. dp[i][0] = min(dp[i-1][0], dp[i-1][2]);
  62. dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + b;
  63. dp[i][2] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) + 2*b;
  64. done = 1;
  65. }
  66. if(ls2 == a && !done){
  67. dp[i][0] = min(dp[i-1][0], dp[i-1][1]);
  68. dp[i][1] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) + b;
  69. dp[i][2] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) + 2*b;
  70. done = 1;
  71. }
  72. if(!done){
  73. dp[i][0] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
  74. dp[i][1] = dp[i][0] + b;
  75. dp[i][2] = dp[i][1] + b;
  76. }
  77. ls0 = a;
  78. ls1 = a+1;
  79. ls2 = a+2;
  80. }
  81. }
  82. cout << min(min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]) << '\n';
  83. }
  84. return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement