YbtOJ 474「决策单调性优化 dp」网格选点

(Updated: )
oi
, , ,

题目链接：YbtOJ #474

小 A 有一张 $T\times T$ 的网格图，左下角为 $(0,0)$，右上角为 $(T,T)$，他在其中指定了 $n$ 个关键点，保证任意两个关键点不同行且不同列。

你可以从中选出若干个关键点，但需要满足每个点都在前一个点的右上方（即横纵坐标都大于前一个点）。

要求在 选出点数尽可能多 的前提下，求出 相邻 两关键点（包括第一个关键点与 $(0,0)$，最后一个关键点与 $(T,T)$）所夹矩形面积之和的最小值。

定义两点 $(x_1,y_1),(x_2,y_2)$（$x_1\le x_2$，$y_1\le y_2$） 所夹矩形面积为 $(x_2-x_1)\times(y_2-y_1)$。

$n\le2\times10^5,T\le10^6$，保证所有 $x$ 各不相同，所有 $y$ 各不相同。

Solution

首先按照横坐标排序，那么我们能选出的点的纵坐标形成一个上升子序列。

现在要求选出点数尽可能多，就是要求最长上升子序列。

我们记 $f_i$ 表示以 $i$ 为结尾的最长上升子序列长度，则根据 LIS 问题的经典理论，我们必须要对于每个 $f_i$ 选出恰好一个点 $w_{f_i}$，满足 $w_{f_i}$ 在 $w_{f_i-1}$ 的右上方。因此对于这道题我们可以分层转移。

考虑 $f_i$ 相同的若干个点，由于我们之前已经按横坐标排过序了，因此它们的纵坐标肯定递减（否则，它们之间就存在转移关系，$f_i$ 不可能相同）。

而对于 $p_i$，上一层的一个点 $p_j$ 能转移到 $p_i$，需要满足 $p_j$ 的两维坐标都小于 $p_i$，因此转移范围应该是上一层的所有点中的一段区间。

于是我们利用线段树分治，把 $p_i$ 扔到能转移到它的区间在线段树中对应的节点上，那么这个限制就被化掉了。

这样一来，所有上一层的转移点都能自由地转移到这一层的所有点，问题就简化了许多。

比较两个转移点 $p_j,p_k(j < k)$，判断何时 $j$ 优于 $k$：

$$
f_j+(x_i-x_j)(y_i-y_j) < f_k+(x_i-x_k)(y_i-y_k)
$$

把 $y_i,x_i$ 看成变量，移项可得：

$$
y_i<\frac{y_j-y_k}{x_k-x_j}x_i+\frac{f_k+x_ky_k-f_j-x_jy_j}{x_k-x_j}
$$

即，使得 $j$ 优于 $k$ 的 $(x_i,y_i)$ 位于一条斜率为正的直线右下方的一个半平面，具有决策单调性。

但要注意，这里的决策单调性是这一层越靠后的位置，越可能选择上一层靠前的位置。

总之怎么判断是否具有决策单调性还是直接打表比较方便。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e6+100;Cn LL inf=1e12;
int n,Tt,f[N],Ans;LL ans=inf,dp[N];
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
PA a[N];
vector<int> v[N],G[N];
#define pb push_back
class BIT{
    private:
        int T[N];
    public:
        I void U(CI p,CI v){RI i;for(i=p+1;i<=Tt+1;i+=i&-i) T[i]=max(T[i],v);}
        I int Q(CI p){RI i,S=0;for(i=p+1;i;i-=i&-i) S=max(S,T[i]);return S;}
}T;
#define mid (l+r>>1)
I void Sol(CI L,CI R,CI l,CI r,CI x,CI d){
    if(l>r) return ;RI i,id=0;LL Mn=inf;
    for(i=L;i<=R;i++) dp[v[d-1][i]]+1LL*(a[G[x][mid]].fi-a[v[d-1][i]].fi)*(a[G[x][mid]].se-a[v[d-1][i]].se)<Mn&&
        (Mn=dp[v[d-1][i]]+1LL*(a[G[x][mid]].fi-a[v[d-1][i]].fi)*(a[G[x][mid]].se-a[v[d-1][i]].se),id=i);
    dp[G[x][mid]]=min(dp[G[x][mid]],Mn);
    Sol(id,R,l,mid-1,x,d),Sol(L,id,mid+1,r,x,d);
}
class SegmentTree{
    private:
        #define PT CI x,CI l,CI r
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
    public:
        I void U(CI p,CI d,PT){
            #define chk(o) (a[o].fi<a[p].fi&&a[o].se<a[p].se)
            if(a[v[d-1][l]].fi>a[p].fia[v[d-1][r]].se>a[p].se) return ;if(chk(v[d-1][l])&&chk(v[d-1][r])) return void(G[x].pb(p));U(p,d,LT),U(p,d,RT);
        }I void Q(CI d,PT){if(Sol(l,r,0,G[x].size()-1,x,d),G[x].clear(),l==r) return ;Q(d,LT),Q(d,RT);}
}S;
int main(){
    freopen("grid.in","r",stdin),freopen("grid.out","w",stdout);
    RI i;for(read(n,Tt),i=1;i<=n;i++) read(a[i].fi,a[i].se);a[++n]=MP(0,0),a[++n]=MP(Tt,Tt);for(sort(a+1,a+n+1),i=1;i<=n;i++) f[i]=T.Q(a[i].se)+1,T.U(a[i].se,f[i]),v[f[i]].pb(i);
    for(i=1;i<=n;i++) Ans=max(Ans,f[i]),dp[i]=f[i]>1?inf:0LL;for(i=2;i<=Ans;S.Q(i,1,0,v[i-1].size()-1),i++) for(auto j:v[i]) S.U(j,i,1,0,v[i-1].size()-1);
    for(i=1;i<=n;i++) f[i]==Ans&&(ans=min(ans,dp[i]));return writeln(ans),0;
}