前言

然而丝之鸽还是没有出

---

正题

题目链接:https://www.luogu.com.cn/problem/P6047

---

题目大意

两个平行的线，上面连接着若干条弦，第$i$条连接上方的$x_i$个下方的$y_i$。
然后每次可以选择一个位置$(i,j)$，可以切断任何位于位置$(u,v)$的弦仅当满足条件$(u>i,v<j)$，消耗代价为$a_i\ast b_j$。

求切断所有线的最小代价。

---

解题思路

如果我们将下面那条线翻转过来，我们就有条件$(u>i,v>j)$，我们将弦看成坐标的话，我们可以发现其实就是每次选择一个点然后将右下角的点都去掉。

所以就有以下优化

如果一个弦代表的点在其他弦代表点的右下角，那么该点不影响结果。可以去掉

如果一个点的代价比他右上角的其中一个点的代价高，那么必定选那个点更优。所以我们可以对于$a$和$b$都取一个前缀$min$

做完以下优化后，对于弦我们可以求到$x$递增，$y$递减的序列。转换到之后就是$a_x$递减，$b_y$递增的序列，可以进行$dp$。
$$f_i=min\{f_j,f_j+a_{x_j+1}{b}_{y_i}\}$$
考虑斜率优化
$$f_i=f_j+a_{x_j+1}{b}_{y_i}$$
转换成函数
$$f_j=-a_{x_j+1}{b}_{y_i}+f_i$$

斜率为$-b_{y_i}$要求截距最小，维护下凸壳（斜率递增）。

然后因为都是单调的，可以用单调队列维护。

---

$code$

#include<cstdio> #include<algorithm> #define ll long long using namespace std; const ll N=3e5+10; struct node{ll x,y; }a[N]; ll n,m,q[N]; double x[N],y[N],f[N]; bool cmp(node x,node y) {return (x.x==y.x)?(x.y<y.y):(x.x<y.x);} double slope(ll i,ll j){if(a[i+1].x==a[j+1].x)return 1e18;return (f[i]-f[j])/(a[j+1].x-a[i+1].x); } int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lf",&x[i]);for(ll i=n;i>=1;i--)scanf("%lf",&y[i]);x[0]=y[0]=1e18;for(ll i=1;i<=n;i++)x[i]=min(x[i],x[i-1]),y[i]=min(y[i],y[i-1]);for(ll i=1;i<=m;i++)scanf("%lld%lld",&a[i].x,&a[i].y),a[i].y=n-a[i].y+1;sort(a+1,a+1+m,cmp);ll p=0;a[0].y=2147483647/3;for(ll i=1;i<=m;i++)if(a[i].y<a[p].y)a[++p]=a[i];m=p;ll l=1,r=1;for(ll i=1;i<=m;i++)a[i].x=x[a[i].x-1],a[i].y=y[a[i].y-1];for(ll i=1;i<=m;i++){while(l<r&&slope(q[l],q[l+1])<=a[i].y)l++;ll pos=q[l];f[i]=f[pos]+a[pos+1].x*a[i].y;while(l<r&&slope(q[r-1],q[r])>slope(q[r],i))r--;q[++r]=i;}printf("%.0lf",f[m]); }

总结

以上是生活随笔为你收集整理的P6047-丝之割【斜率优化,dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。