Codeforces - D. Make The Fence Great Again
12822 단어 Codeforces동적 기획
time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output
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≤3⋅105) — the number of queries.
The first line of each query contains one integers n (1≤n≤3⋅105) — 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≤109) — 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 3⋅105.
It is guaranteed that answer to each query will not exceed 1018.
Output For each query print one integer — the minimum number of rubles you have to spend to make the fence great.
Example inputCopy 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.
하나의 선형 dp, 이 문제의 중요한 요점은 울타리가 최대 두 번 높아지지 않는다는 것이다. 극한 상황을 고려하면 세 개 등 높은 상황이 이어지고 최대 두 번 높아지는 것을 알기 어렵지 않다.
그래서 우리는 dp[i][j]로 현재 i번째 울타리에 있고 i번째 울타리가 j번 높아지는 최소한의 대가를 고려하면 된다는 것을 나타낸다.
AC 코드:
#pragma GCC optimize(2)
#include
#define int long long
using namespace std;
const int N=3e5+10;
int q,n,dp[N][3],a[N],b[N];
signed main(){
scanf("%lld",&q);
while(q--){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld %lld",&a[i],&b[i]);
for(int i=0;i<3;i++) dp[1][i]=i*b[i];
for(int i=2;i<=n;i++){
for(int j=0;j<3;j++){
dp[i][j]=-1;
for(int k=0;k<3;k++){
if(dp[i-1][k]==-1) continue;
if(a[i-1]+k==a[i]+j) continue;
if(dp[i][j]==-1||dp[i][j]>dp[i-1][k]+b[i]*j)
dp[i][j]=dp[i-1][k]+b[i]*j;
}
}
}
int res=0x3f3f3f3f3f3f3f3f;
for(int i=0;i<3;i++){
if(dp[n][i]!=-1) res=min(res,dp[n][i]);
}
printf("%lld
",res);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 1287C Garland제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.