题解

已知序列$a_1,a_2,…, a_n$，对于$a_i$，可以花费$b_i$的代价将$a_i$增加$1$，花费$c_i$的代价将$a_i$减小$1$，求将序列$a$变为非严格单调递增的最小代价。

最朴素的动态规划：设$f_{i,j}$表示只考虑前$i$个位置，且$a_i$的值变为$j$时的最小代价。

$$f_{i,j}=min_{k<=j}f_{i-1,k}+(a_i-j)*c_i \ (a_i\geq j)$$

$$f_{i,j}=min_{k<=j}f_{i-1,k}+(j-a_i)*b_i \ (a_i\leq j)$$

设$pre_{i,j}=min_{k<=j}f_{i,k}$

则上文中动态规划方程变为：

$$f_{i,j}=pre_{i-1,j}+(a_i-j)*c_i \ (a_i\geq j)$$

$$f_{i,j}=pre_{i-1,j}+(j-a_i)*b_i \ (a_i\leq j)$$

可以将$j$看作横坐标，$f_{i,j}$看为纵坐标，则通过归纳法（证明的过程实际就是下述维护函数的过程）可证明该函数是凹函数，斜率单调不降。

因此，可以将解题过程分为两步：

在函数中将$f_{i-1,j}$替换为$pre_{i-1,j}$，由于$f$为凹函数，因此可以通过在栈中维护函段将所有栈顶斜率大于$0$的线段替换为一个斜率等于$0$的线段。
将函数$pre_{i-1}$与函数$|a_i-j|*(a_i\geq j\ ?\ c_i\ : \ b_i)$（显然该函数为$V$形）求和，得到$f_i$。可以通过在栈中维护斜率变换处和斜率变化值来维护，显然将$pre$与$V$形函数求和只会在$a_i$处插入一个斜率变换值$b_i+c_i$。（注意同时要维护第一条线段的斜率和最后一条线段的斜率）

重复以上两步$n$次，得到$f_n$的函数图象，然后算出$f_{n,min { a_i}}$的函数值（显然，将所有$a_i$变为最小值即可），再通过函数图象递推出所有斜率变化处的函数值，取最小值即可得到答案。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+1;
 
int T;
int n;
ll a[N],b[N],c[N];
multiset<pair<ll,ll>> s;
 
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
		for(int i=1;i<=n;++i)scanf("%lld",&b[i]);
		for(int i=1;i<=n;++i)scanf("%lld",&c[i]);
		ll lk=0,rk=0;
		s.clear();
		s.insert({0,0});
		ll now=0;
		for(int i=1;i<=n;++i){
			while(rk>0){
				assert(s.size());
				auto p=prev(s.end());
				ll x=p->first,val=p->second;
				s.erase(p);
				rk-=val;
				if(rk<=0){
					s.insert({x,-rk});
					rk=0;
					break;
				}
			}
			lk-=c[i];
			rk+=b[i];
			s.insert({a[i],b[i]+c[i]});
			now+=a[i]*c[i];
		}
		ll ans=now,last=0,k=lk;
		for(auto p:s){
			now+=k*(p.first-last);
			last=p.first;
			k+=p.second;
			ans=min(ans,now);
		}
		assert(k==rk);
		printf("%lld\n",ans);
	}
}

序列单调递增的最小代价

题解

代码