决策单调性分治

11490DX Re: Master Lv.15
  2024-11-07 19:52:03 2024-11-07 19:52:03 Created   2025-02-14 13:04:54 2025-02-14 13:04:54 Updated      3k Words  13 Mins  

 

决策单调性分治，就是根据一个序列的决策单调性来分治找出序列中每个位置的答案。

什么是决策单调性？就是点 的决策点随着 递增也单调不降。根据这个单调性我们就可以先找到序列中间点的决策点，再左右分治。

用一道例题来说明什么是决策单调性。

P3515 Lightning Conductor

给定一个长度为 的序列 ，对于每个 ，求出一个最小的非负整数 ，使得 ，都有 。

， 。

思路：

要找到最小的非负整数 ，我们可以首先把 的表达式表示出来。

因为 ，移项，可得 。我们需要找对于每一个属于区间 的 对应的这个 ，并且还要找 的最小值。那么就可以推出：

（因为 固定不变）。

但是这个绝对值看着很烦，于是我们把绝对值去掉，再先让 不保留整数（可以最后再取 ceil）：

总之，就是把他拆成两段分开算 max。这个只需要把区间 反转一遍再重新算然后取 max 就行了。这样就可以只考虑前半段：

OK。现在我们称每一个 为 的决策点，而使 能够到达最大值的决策点为 的最优决策点。我们设它为 。我们现在来求一下这个最优决策点的性质。

要从 转移到 ，先找两个点举例子。我们设有两个点 和 ，，现在我们要把这个东西转移到 。则他的转移量 。前面两项好比大小，但是最后的这个根号又该怎么算值呢？

可以数形结合： 的图像长什么样？

可以发现，当 越大，曲线就越平缓。可以推出来当 时， 。于是对比 和 ，发现前面的两项是可以消去的，若 ，则 ，则 。

这时我们把 代入 点，我们可以发现，若 ，就算 ，最优决策点不动， 也不如 优（因为 ）。所以第 个点对应的最优决策点 一定大于等于 。然后 ，……

发现了什么？ 序列有单调性！这就是前面所说的决策单调性。知道了 序列的决策单调性，就可以用前面的决策单调性分治：

  1. 首先设区间 的最佳决策点范围是 。
  2. 设一个变量 mid = l+r>>1，暴力扫区间 （取 min 是为了保证不会根号下负数） 找到它的最佳决策点 。
  3. 给 赋值（取 max）。因为已经确定了 的 值，所以将区间分为 和 继续分治。它们的最佳决策点范围分别是 和 。
  4. 分治完了之后将区间反转，再分治一遍，再反转回来，即可得到答案。
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
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
double dp[N];
//dp[i] 表示在i这个位置的最大的p值
int n, a[N];
void solve(int l, int r, int x, int y){
    int mid = l+r>>1;
    if(l>r) return ;
    int pos = 0;
    double ans = -0x7fffffff;
    for(int i=x;i<=min(mid, y); i++){
        double nowval = a[i]-a[mid]+sqrt(mid-i);
        if(nowval > ans){
            ans = nowval;
            pos = i;
        }
    }
    dp[mid] = max(dp[mid], ans);
    if(l==r) return ;
    solve(l, mid-1, x, pos);
    solve(mid+1, r, pos, y);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    solve(1, n, 1, n);
    reverse(a+1, a+1+n), reverse(dp+1, dp+1+n);
    solve(1, n, 1, n);
    reverse(a+1, a+1+n), reverse(dp+1, dp+1+n);
    for(int i=1;i<=n;i++){
        cout<<int(ceil(dp[i]))<<'\n';
    }
    return 0;
}

P3140 Circular Barn Revisited G

虽然这道题不是一道决策单调性分治，但是它会为下一道题提供思路：

因为 ，所以可以想到可以 DP，先不考虑复杂度。

我们可以想新增一个入口会对后面的造成什么影响：

在新增了一个入口之后，在这个入口顺时针方向的这些牛就会缩短他和外界的距离，所以我们可以预处理出从一个打开入口 ，让 所有牛群都能进来的最小代价的数组 ：

于是我们可以根据这个来设状态：

代表：现在从 扫到了 ，一共开了 扇门时使 的牛全部回到原位所需的代价是多少。

转移方程：

也就是，我们枚举第 道门是在 位置开的，我们转移就把 分为两段：

第一段 就可以直接从 转移，就是前面一段，开了 道门，并且只扫到 的答案。

第二段 就是从 位置的入口进入把 的位置填满，让 的所有牛群都进来，他的代价就是 。

把他们两个相加就是这个状态的代价了。

但是由于原题是一个环，我们只能破环为链，枚举每一个起点，取所有起点的 终点 的最小值。

时间复杂度 ，可以通过本题。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 104<<1;
int dp[N][8];
int dist[N][N];
/*Dist[i][j]:
将再点i的入口放开，让所有在i~j的奶牛全部回到原来的位置上所需的代价之和
*/
int n; 
int r[N], klim;
signed main(){
    // freopen("P3140_2.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>klim;
    for(int i=1;i<=n;i++){
        cin>>r[i];
        r[i+n] = r[i];
    }

    for(int i=1;i<=2*n;i++){
        int sum = 0;
        for(int j=0;j<n&&i+j<=2*n;j++){
            
            int nowpos = i+j;
            sum += j * r[nowpos];
            dist[i][nowpos] = sum;
            
        }
    }
    int ans = 0x3f3f3f3f;
    for(int l=1;l<=n;l++){
        // 枚举从哪个点开始
        memset(dp, 0x3f, sizeof dp);
        dp[l-1][0] = 0;
        //dpi,j:现在从l扫到了i，现在开了第j道门
        int r = l+n-1;
        for(int k=1;k<=klim;k++){
            // 枚举现在开了多少道门
            for(int j=l;j<=r;j++){
                // 枚举现在的位置
                for(int p=l;p<j;p++){
                    // 枚举第k道门是在p位置开的
                    dp[j][k] = min(dp[j][k], dp[p-1][k-1]+dist[p][j]);
                    // cerr<<j<<' '<<k<<' '<<dp[j][k]<<'\n';
                }

            }
        }
        cerr<<r<<' '<<dp[r][klim]<<'\n';
        ans = min(ans, dp[r][klim]);
    }
    cout<<ans<<'\n';
    return 0;
}

P6173 Circular Barn P

这道题与上一道题的不同之处就是： 的范围变了。。上一道题的 无法通过。我们看怎么优化这个算法。

我们想一想，当 的 变大时，使 最小的那个决策点 又是如何变化的？

感性理解一下， 一直在变大，区间一直在变大。如果 不变的话，那么右边的牛群就越来越多。这个时候只能将 向右边移动来减小右边的这个变化量。所以当 递增， 也会单调不降。又是决策单调性优化！

然后还是枚举每一个起点，是 ，枚举每一个 ，就是 ，决策单调性分治，就是 。所以总复杂度就是 ，可以通过本题。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3+4;
ll dist[N][N];
ll dp[N][8];

int n, klim;
ll r[N];

void solve(int k, int l, int r, int x, int y){
    if(l>r) return ;
    int mid = l+r>>1;
    ll ans = 0x3f3f3f3f3f;
    ll pos;
    for(int i=x;i<=min(y, mid);i++){
        ll nowans = dp[i-1][k-1] + dist[i][mid];
        if(nowans < ans){
            pos = i;
            ans = nowans;
        }
    }
    // cerr<<k<<" : "<<mid<<" -> "<<pos<<"( "<<ans<<" ) and range from "<<x<<" to "<<y<<'\n';
    dp[mid][k] = ans;
    if(l==r) return;
    solve(k, l, mid-1, x, pos);
    solve(k, mid+1, r, pos, y);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>klim;
    for(int i=1;i<=n;i++){
        cin>>r[i];
        r[i+n] = r[i];
    }
    
    for(int i=1;i<=2*n;i++){
        ll sum = 0;
        for(int j=0;i+j<=2*n&&j<=n;j++){
            int nowpos = i+j;
            sum += j*r[nowpos];
            dist[i][nowpos] = sum;
        }
    }
    // cerr<<dist[1][2]<<'\n';
    ll ans = 0x3f3f3f3f3f;
    for(int l=1;l<=n;l++){
        int r = l+n-1;
        for(int i=l;i<=r;i++){
            dp[i][0] = 0x3f3f3f3f3f;
        }
        dp[l-1][0] = 0;
        for(int k=1;k<=klim;k++){
            solve(k, l, r, l, r);
        }
        cerr<<r<<' '<<dp[r][klim]<<'\n';
        ans = min(ans, dp[r][klim]);
    }
    cout<<ans<<'\n';
}

P10967/P4767 邮局

前面是简单版，后面是加强版。

首先要求最简单的 DP 该怎么做。

如果你对某一个区间加了一个邮局，那么这个邮局该怎么放才能使区间到这个邮局的距离最小呢？我们发现这个就是一个绝对值方程：

要求这个玩意的最小值，回顾初中数学，发现这个邮局的位置设在中位数就可以得到答案。所以我们可以处理这个中位数的 和 （ 就是 ， 就是 ），然后把 和 加起来就可以得到在一个区间放一个邮局所需的最小距离了（可以自己手推式子）。

我们设刚刚说的最小距离为 ，知道了这个玩意之后，就可以很好的推出 DP 式子了。

我们设 为「考虑范围」为 的所有村庄，设点 个邮局的最小距离总和（就是题目里让我们求的那个）。然后加上前面的 ，我们可以得到：

就是把这个 分成两部分：

第一部分是前面的 ，是已知的 。

第二部分就是后面的 ，这一部分我们给他设一个邮局，然后所需的最小代价就是 。

边界就设 ，因为就算再多邮局来了，你也一个都管不到。

于是就可以用这种方法 DP 过简单版。时间复杂度为 。

但是复杂版的 ，不能过，考虑怎么优化。

假设我们之前在求 的时候已经设好了最优的邮局选址在下标为 的村庄，那么我们现在求 的时候，如果你还是选下标为 的村庄不动，那么你右边的村庄就会越来越多，这个时候你只能把 往右移动以达到距离最小。所以发现，当 增加的时候， 也在单调不降。说明可以用决策单调性分治来做。

时间复杂度 。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 3004;
int dp[N][N];
int pre[N][N], suf[N][N];
//算一个区间的绝对值方程可以取中间点，然后算sufsum[mid~l]+presum[mid~r];
int n, m;
int a[N];
#define dist(i,j) suf[i+j>>1][i]+pre[i+j>>1][j]

void solve(int k, int l, int r, int x, int y){
    if(l>r) return ;
    int mid = l+r>>1;
    int ans = 0x3f3f3f3f, pos;
    for(int i=x;i<=min(mid, y);i++){
        int nowans = dp[i-1][k-1] + dist(i, mid);
        if(nowans < ans){
            ans = nowans;
            pos = i;
        }
    }
    dp[mid][k] = ans;
    if(l==r) return ;
    solve(k, l, mid-1, x, pos);
    solve(k, mid+1, r, pos, y);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1, a+1+n);
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            pre[i][j] = pre[i][j-1] + a[j] - a[i];
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=i;j>=1;j--){
            suf[i][j] = suf[i][j+1] + a[i] - a[j];
        }
    }
    memset(dp, 0x3f, sizeof dp);
    for(int i=0;i<=n;i++){
        dp[0][i]=0;
    }
    //当处理的范围是1~0时，就算不管多少个邮局也是0
    for(int p=1;p<=m;p++){
        solve(p, 1, n, 1, n);
    }

    cout<<dp[n][m];
    return 0;
}
  • Title: 决策单调性分治
  • Author: 11490DX
  • Created at : 2024-11-07 19:52:03
  • Updated at : 2025-02-14 13:04:54
  • Link: https://11490dx.net/2024/11/07/div-and-con1/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
决策单调性分治
  1. P3515 Lightning Conductor
    1. 思路：
  2. P3140 Circular Barn Revisited G
  3. P6173 Circular Barn P
  4. P10967/P4767 邮局