前言

然而絲之鴿還是沒有出

---

正題

題目鏈接:https://www.luogu.com.cn/problem/P6047

---

題目大意

兩個平行的線，上面連接著若干條弦，第$i$條連接上方的$x_i$個下方的$y_i$。
然后每次可以選擇一個位置$(i,j)$，可以切斷任何位于位置$(u,v)$的弦僅當滿足條件$(u>i,v<j)$，消耗代價為$a_i?b_j$。

求切斷所有線的最小代價。

---

解題思路

如果我們將下面那條線翻轉過來，我們就有條件$(u>i,v>j)$，我們將弦看成坐標的話，我們可以發(fā)現(xiàn)其實就是每次選擇一個點然后將右下角的點都去掉。

所以就有以下優(yōu)化

如果一個弦代表的點在其他弦代表點的右下角，那么該點不影響結果。可以去掉

如果一個點的代價比他右上角的其中一個點的代價高，那么必定選那個點更優(yōu)。所以我們可以對于$a$和$b$都取一個前綴$min$

做完以下優(yōu)化后，對于弦我們可以求到$x$遞增，$y$遞減的序列。轉換到之后就是$a_x$遞減，$b_y$遞增的序列，可以進行$dp$。
$$f_i=min\{f_j,f_j+a_{x_j+1}{b}_{y_i}\}$$
考慮斜率優(yōu)化
$$f_i=f_j+a_{x_j+1}{b}_{y_i}$$
轉換成函數(shù)
$$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】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。