Link: D. Make The Fence Great Again

D. Make The Fence Great Again

Description:
You have a fence consisting of n vertical boards. The width of each board is 1. The height of the i-th board is ai. You think that the fence is great if there is no pair of adjacent boards having the same height. More formally, the fence is great if and only if for all indices from 2 to n, the condition ai−1≠ai holds.

Unfortunately, it is possible that now your fence is not great. But you can change it! You can increase the length of the i-th board by 1, but you have to pay bi rubles for it. The length of each board can be increased any number of times (possibly, zero).

Calculate the minimum number of rubles you have to spend to make the fence great again!

You have to answer q independent queries.

Input
The first line contains one integer q (1≤q≤3e5) — the number of queries.

The first line of each query contains one integers n (1≤n≤3e5) — the number of boards in the fence.

The following n lines of each query contain the descriptions of the boards. The i-th line contains two integers ai and bi (1≤ai,bi≤1e9) — the length of the i-th board and the price for increasing it by 1, respectively.

It is guaranteed that sum of all n over all queries not exceed 3e5.

It is guaranteed that answer to each query will not exceed 1e18.

Output
For each query print one integer — the minimum number of rubles you have to spend to make the fence great.

Example
input
3
3
2 4
2 1
3 5
3
2 3
2 10
2 6
4
1 7
3 3
2 6
1000000000 2
output
2
9
0
Note
In the first query you have to increase the length of second board by 2. So your total costs if 2⋅b2=2.

In the second query you have to increase the length of first board by 1 and the length of third board by 1. So your total costs if 1⋅b1+1⋅b3=9.

In the third query the fence is great initially, so you don't need to spend rubles.

Problem solving:
这道题的意思就是给你一个由多个栅栏组成的木板，给你每块木板的高度以及它每增加一单位高度需要耗费的卢布（rubles）。现在问你如何在保证所有的相邻的木板高度都不同的情况下耗费最少的卢布数，让你输出这个最小的花费。
先添一波BLY！！！


我们考虑如果有相邻的数相等，那么其中任意一个加一就行，但是它加一之后有可能会跟另一个方向上相邻的数字相等，所以每个木板只有三种情况，不加，加一或者加二。我们设置一个二维数组dp[maxn][3],表示第i个木板之前的所有木板达到要求需要耗费的卢布数。开始时初始化为一个极大值。然后一直转移下去。因为前面的如果有变化所以可能也会导致后面的情况有变化，所以需要用的dp。
转移方程: dp[i][k] = min(dp[i][k], dp[i - 1][j] + k * b[i]) 能用到这个转移方程必须有一个前提条件：a[i - 1] + j != a[i] + k
最后我们只需要输出dp[n-1][0]([1],[2])中的最小值就行了。

输入输出数据比较多，所以直接用cin会超时（枯了）。可以关闭同步流用cin或者直接用scanf。唉，scanf大法好啊！！！

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 3e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll       a[maxn], b[maxn], dp[maxn][3];
int main()
{
    ll q, n;
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin >> q;
    while (q--)
    {
        cin >> n;
        for (ll i = 0; i < n; i++)
            cin >> a[i] >> b[i];
        for (ll i = 0; i < n; i++)
            for (ll j = 0; j < 3; j++)
                dp[i][j] = inf;
        dp[0][0] = 0, dp[0][1] = b[0], dp[0][2] = b[0] * 2;
        for (ll i = 1; i < n; i++)
            for (ll j = 0; j < 3; j++)
                for (ll k = 0; k < 3; k++)
                    if (a[i - 1] + j != a[i] + k)
                        dp[i][k] = min(dp[i][k], dp[i - 1][j] + k * b[i]);

        cout << min(dp[n - 1][0], min(dp[n - 1][1], dp[n - 1][2])) << endl;
    }
return 0;
}
赏