Comet OJ - Contest #8 C.符文能量

题目链接
思路：我们考虑合并区间 $[l,r]，r\>l$[l,r]，r>l在不精炼的情况下的贡献是一定的，我们用数组 $A$A记录这个的前缀和，
用数组 $L$L记录以 $i$i结尾的精炼一个后缀的最小贡献，
那么 $L\left[i\right]=min\left(L\right[i-1]+k\ast k\ast p[i-1].b\ast p[i].a,A[i-1]+k\ast p[i-1].b\ast p[i\left].a\right)$L[i]=min(L[i−1]+k∗k∗p[i−1].b∗p[i].a,A[i−1]+k∗p[i−1].b∗p[i].a)
然后枚举每个 $i$i作为右端点，计算这个位置的最小贡献
贡献为：
$1.A\left[n\right]-A[i+1]$1.A[n]−A[i+1]意为后面不精炼的和
$2.p\left[i\right].b\ast k\ast p[i+1].a$2.p[i].b∗k∗p[i+1].a意为这个位置精炼后和后面的一个合并的新贡献
$3.L\left[i\right]$3.L[i]表示最小的前缀

然后和不精炼时取个最小值即可

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int n,k;
struct uzi
{
    LL a,b;
}p[N];
LL A[N],ans=1e18,L[N],R[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>p[i].a>>p[i].b;
    for(int i=2;i<=n+1;i++)A[i]=1ll*p[i].a*p[i-1].b+A[i-1];//不改变总数的这么多
    L[0]=0;
    for(int i=1;i<=n+1;i++)L[i]=min(L[i-1]+1ll*k*k*p[i-1].b*p[i].a,A[i-1]+1ll*k*p[i-1].b*p[i].a);//表示精炼左区间端点在i时，[1,i)的最小贡献
    for(int i=1;i<=n;i++){//枚举右端点
        LL res=A[n]-A[i+1];
        res+=1ll*p[i].b*k*p[i+1].a;
        res+=L[i];
        ans=min(ans,res);
    }
    cout<<min({ans,L[n],A[n]})<<endl;
    return 0;
}