Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef pair <int, int> pii;
- typedef tuple<int, int, int> tiii;
- typedef tuple<int, int, int, int> tiiii;
- #define F(i, a, b) for(int i = a; i <= (int)b; i++)
- #define f(i, a, b) for(int i = a; i >= (int)b; i--)
- #define wh(n) int iteration = n; while(iteration--)
- #define For(t, it) for(auto it = (t).begin(); it != (t).end(); ++it)
- #define IN insert
- #define PB push_back
- #define MP make_pair
- #define MT make_tuple
- int main(){
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int q;
- cin >> q;
- wh(q){
- ll n, a, b;
- cin >> n;
- ll dp[n][3];
- ll ls0, ls1, ls2;
- F(i, 0, n-1){
- cin >> a >> b;
- if(!i){
- ls0 = a;
- ls1 = a+1;
- ls2 = a+2;
- dp[i][0] = 0;
- dp[i][1] = b;
- dp[i][2] = 2*b;
- }else{
- bool done = 0;
- if(ls0 == a && !done){
- dp[i][0] = min(dp[i-1][1], dp[i-1][2]);
- dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + b;
- dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + 2*b;
- done = 1;
- }
- if(ls0 == a+1 && !done){
- dp[i][0] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
- dp[i][1] = min(dp[i-1][1], dp[i-1][2]) + b;
- dp[i][2] = min(dp[i-1][0], dp[i-1][2]) + 2*b;
- done = 1;
- }
- if(ls0 == a+2 && !done){
- dp[i][0] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
- dp[i][1] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) + b;
- dp[i][2] = min(dp[i-1][2], dp[i-1][1]) + 2*b;
- }
- if(ls1 == a && !done){
- dp[i][0] = min(dp[i-1][0], dp[i-1][2]);
- dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + b;
- dp[i][2] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) + 2*b;
- done = 1;
- }
- if(ls2 == a && !done){
- dp[i][0] = min(dp[i-1][0], dp[i-1][1]);
- dp[i][1] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) + b;
- dp[i][2] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) + 2*b;
- done = 1;
- }
- if(!done){
- dp[i][0] = min(min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
- dp[i][1] = dp[i][0] + b;
- dp[i][2] = dp[i][1] + b;
- }
- ls0 = a;
- ls1 = a+1;
- ls2 = a+2;
- }
- }
- cout << min(min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]) << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement