題目鏈接

https://www.luogu.com.cn/problem/P5244

題解

首先求出 LIS. 根據(jù) LIS 的值我們可以對(duì)整個(gè)點(diǎn)集分層，每一層內(nèi)進(jìn)行 DP. 將每層的點(diǎn)按 \(x_i\) 從小到大排序，那么顯然一層內(nèi)的 \(y_i\) 是遞減的。設(shè)第 \(d\) 層的點(diǎn)集為 \(L_d\).
那么上一層某點(diǎn)能轉(zhuǎn)移到的該層的點(diǎn)是一段區(qū)間，能轉(zhuǎn)移到該層某點(diǎn)的上一層的點(diǎn)也是一段區(qū)間。設(shè)能轉(zhuǎn)移到該層 (第 \(d\) 層) \(i\) 點(diǎn)的上一層的點(diǎn)區(qū)間為 \([l_i,r_i]\) 且 \([l_i,r_i]\in L_{d-1}\), 則轉(zhuǎn)移方程為 \(f[i]=\min_{j\in [l_i,r_i]}(f(d-1,j)+(x_i-x_j)(y_i-y_j))\).
現(xiàn)在我們證明這個(gè) DP 有決策單調(diào)性: 設(shè)同一層的兩點(diǎn) \((x_1,y_1),(x_2,y_2)\in L_{d-1}\) 滿足\(x_1<x_2,y_1>y_2\), 那么轉(zhuǎn)移到的點(diǎn) \(x\) 越大時(shí)，\((x_2,y_2)\) 相對(duì)于 \((x_1,y_1)\) 越優(yōu)。設(shè)二者的 \(f\) 值分別為 \(f_1,f_2\), 轉(zhuǎn)移到的點(diǎn)為 \((x,y)\), 二者作差可得 \(f_1+(x-x_1)(y-y_1)-f_2-(x-x_2)(y-y_2)\), 去掉與 \(x,y\) 無關(guān)的部分后整理得 \(x(y_2-y_1)+y(x_2-x_1)\). 由于 \(x\) 單調(diào)增，\((y_2-y_1)\) 為負(fù)數(shù)，\(y\) 單調(diào)減，\((x_2-x_1)\) 為正數(shù)，故該式值單調(diào)減，因此一定存在一個(gè)位置滿足它前面的 \((x_2,y_2)\) 更優(yōu)，后面的 \((x_1,y_1)\) 更優(yōu) (前、后都指按 \(x\) 從小到大排序)，證畢。
假設(shè)轉(zhuǎn)移沒有區(qū)間限制，就可以直接用傳統(tǒng)的方法優(yōu)化到 \(O(n\log n)\). 但是這里有轉(zhuǎn)移的區(qū)間限制，于是一個(gè)直接的方法是用線段樹維護(hù)，對(duì)上一層建線段樹，線段樹的每個(gè)區(qū)間使用傳統(tǒng)的方法跑一遍決策單調(diào)性，時(shí)間復(fù)雜度 \(O(n\log^2 n)\).
但是官方題解給了個(gè)更妙的做法: 由于這里 \(l_i\) 和 \(r_i\) 都是單調(diào)遞增的，我們可以把上一層分為若干個(gè)區(qū)間，滿足每個(gè) \([l_i,r_i]\) 只和不超過 \(2\) 段區(qū)間有交，且和每一段有交的區(qū)間的交都是一段前綴或者后綴。具體的方法是直接對(duì)于當(dāng)前待劃分的區(qū)間的左端點(diǎn) \(l\) 選取左端點(diǎn)不超過 \(l\) 的 \([l_i,r_i]\) 中最大的 \(r_i\) 作為劃分出的第一個(gè)區(qū)間的右端點(diǎn)就可以了。那么我們對(duì)劃分出的每段區(qū)間分別從前往后和從后往前跑一遍傳統(tǒng)方法的決策單調(diào)性，就可以完成 DP 了。
時(shí)間復(fù)雜度 \(O(n\log n)\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator #define pii pair<int,int> using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 2e5+2; const int mxMX = 1e6; const llong INF = 1e13; struct Point {int x,y,w;Point() {}Point(int _x,int _y) {x = _x,y = _y;} } a[mxN+3]; int bit[mxMX+3]; int lb[mxN+3],rb[mxN+3]; int segr[mxN+3]; llong f[mxN+3]; pii que[mxN+3]; vector<int> trans[mxN+3][2]; int n,m,segn; llong mx;bool cmp_xy(Point x,Point y) {return x.x<y.x||(x.x==y.x&&x.y<y.y);} bool cmp_w(Point x,Point y) {return x.w<y.w||(x.w==y.w&&x.x<y.x);}void modify(int u,int x) {u++; while(u<=mx+1) {bit[u] = max(bit[u],x); u+=(u&(-u));}} int query(int u) {u++; int ret = 0; while(u) {ret = max(ret,bit[u]); u-=(u&(-u));} return ret;}llong calc(int i,int j) {return f[i]+1ll*(a[j].x-a[i].x)*(a[j].y-a[i].y);}int main() {scanf("%d%lld",&n,&mx);for(int i=1; i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y); a[++n] = Point(0,0),a[++n] = Point(mx,mx);sort(a+1,a+n+1,cmp_xy);for(int i=1; i<=n; i++){a[i].w = query(a[i].y)+1;modify(a[i].y,a[i].w);m = max(m,a[i].w);}sort(a+1,a+n+1,cmp_w);llong ans = INF; for(int i=1; i<=n; i++) f[i] = INF; f[1] = 0ll;for(int l=2,pl=1,pr=1; l<=n; l++){int r = l; while(r<n&&a[r+1].w==a[l].w) {r++;}for(int i=l,j=pl; i<=r; i++){while(j<pr&&a[j+1].x<=a[i].x) {j++;}rb[i] = j;}for(int i=r,j=pr; i>=l; i--){while(j>pl&&a[j-1].y<=a[i].y) {j--;}lb[i] = j;}segn = 0; segr[0] = pl-1;for(int l2=pl,j=l; l2<=pr; l2++){segn++; int r2 = l2;while(j<=r&&lb[j]<=l2){r2 = max(r2,rb[j]);if(rb[j]>=l2) {trans[segn][0].push_back(j);}if(lb[j]<l2) {trans[segn-1][1].push_back(j);}j++;}segr[segn] = r2;l2 = r2;if(l2==pr){while(j<=r){trans[segn][1].push_back(j);j++;}}}for(int i=1; i<=segn; i++){int hd = 1,tl = 0;for(int j=segr[i-1]+1,k=0; j<=segr[i]; j++){while(tl>=hd&&calc(que[tl].first,que[tl].second)>=calc(j,que[tl].second)) {tl--;}if(tl<hd) {que[++tl] = mkpr(j,r);}else{int left = l-1,right = que[tl].second;while(left<right){int mid = (left+right+1)>>1;if(calc(que[tl].first,mid)>=calc(j,mid)) {left = mid;}else {right = mid-1;}}if(left>=l) {que[++tl] = mkpr(j,left);}}while(k<trans[i][0].size()&&rb[trans[i][0][k]]==j){int pos = trans[i][0][k];while(tl>hd&&calc(que[tl].first,pos)>=calc(que[tl-1].first,pos)) {tl--;}f[pos] = min(f[pos],calc(que[tl].first,pos));k++;}}if(trans[i][1].size()==0) continue;hd = 1,tl = 0;for(int j=segr[i],k=trans[i][1].size()-1; j>segr[i-1]; j--){while(tl>=hd&&calc(que[tl].first,que[tl].second)>=calc(j,que[tl].second)) {tl--;}if(tl<hd) {que[++tl] = mkpr(j,l);}else{int left = que[tl].second,right = r+1;while(left<right){int mid = left+(right-left>>1);if(calc(que[tl].first,mid)>=calc(j,mid)) {right = mid;}else {left = mid+1;}}if(right<=r) {que[++tl] = mkpr(j,right);}}while(k>=0&&lb[trans[i][1][k]]==j){int pos = trans[i][1][k];while(tl>hd&&calc(que[tl].first,pos)>=calc(que[tl-1].first,pos)) {tl--;}f[pos] = min(f[pos],calc(que[tl].first,pos));k--;}}}for(int i=0; i<=segn; i++) trans[i][0].clear(),trans[i][1].clear();pl = l,l = pr = r;}printf("%lld\n",f[n]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Luogu P5244 [USACO2019Feb Platinum] Mowing Mischief (动态规划、决策单调性)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。