算法学习——决策单调性优化DP

update in 2019.1.21 优化了一下文中年代久远的代码的格式……

什么是决策单调性？

在满足决策单调性的情况下，通常决策点会形如1111112222224444445555588888.....

即不可能会出现后面点的决策点小于前面点的决策点这种情况。

那么这个性质应该如何使用呢？

　1，二分。

　　考虑到决策点单调递增，因此我们考虑用单调队列存下当前的决策选取情况。

　　单调队列中存的量会带3个信息：这是哪个决策点，这个决策点会给哪个区间的点产生贡献（这是一个区间，所以算2个信息）

　　相当于队列中存了很多个区间，假设当前的决策点是这样的：1111112222222333333，

　　现在插入4这个决策，那么我们就是要找到最靠左的合法位置将决策序列变为类似这样的序列：111111222222444444444,

　　因为决策单调，所以要覆盖肯定是一整段一整段的覆盖，因此我们先判断4是否可以覆盖完3这个区间，只需要看3的左端点是否可以被替换即可。

　　我们重复覆盖整个区间这个操作，直到有个区间无法被完整覆盖，或者已经到了不合法的位置(因为第x个点只能给区间[x + 1, n]内的点产生贡献)。

　　如果这个区间无法被完整覆盖，那么我们就在这个区间内二分找到最靠左的点使得4可以替换掉这个区间内的数，然后修改管理这个区间的数的区间，把被覆盖的区间让给4.

　　每次操作前弹掉已经没有用的决策点，于是可以实现O(1)转移。(例如当前队首的决策点可以更新[3, x-1]这个区间，但我们已经枚举到x了，所以这个决策点显然就没有什么用了)　　

　　以下是某个年代久远的一道决策单调性优化的代码。

 1 /*[NOI2009]诗人小G by ww3113306*/
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define R register int
 5 #define AC 100100
 6 #define LL long long
 7 #define LD long double
 8 #define ac 101000
 9 #define inf 1000000000000000000LL
10 int t, L, p, n;
11 int Next[AC], s[AC], last[AC], l[AC], r[AC];//对应决策的管理区间,Next对last进行相反操作,以便输出
12 int q[AC], head, tail;//存下当前是哪个决策
13 LD f[AC];
14 LL sum[AC];
15 char ss[ac][45];
16 
17 inline LD qpow(LD x)//error!!!x也要用LD！！！
18 {
19     LD ans = 1;int have = p;
20     while(have)
21     {
22         if(have & 1) ans *= x;
23         x *= x, have >>= 1;
24     }
25     return ans;
26 }
27 
28 inline LD count(int x, int j){return f[j] + qpow(abs(sum[x] - sum[j] - L - 1));}//j --- > x
29 
30 inline void pre()
31 {
32     scanf("%d%d%d", &n, &L, &p);
33     for(R i = 1; i <= n; i ++)
34     {
35         scanf("%s", ss[i] + 1);
36         s[i] = strlen(ss[i] + 1) + 1;//加上后面的空格
37         sum[i] = sum[i-1] + s[i];//求出前缀和
38     }    
39 }
40 
41 void half(int x)//二分查找
42 {
43     int now = q[tail], ll = max(l[now], x + 1), rr = n, mid;//因为可能可以覆盖多个区间
44     while(ll < rr)
45     {
46         mid = (ll + rr) >> 1;
47         if(count(mid, x) < count(mid, now)) rr = mid;//如果更优就往左缩短
48         else ll = mid + 1;//不然就向右寻找
49     }
50     r[q[tail]] = ll - 1;
51     q[++tail] = x, l[x] = ll, r[x] = n;
52 }
53 
54 inline void getans()
55 {
56     head = 1, tail = 1, q[1] = 0, l[0] = 1, r[0] = n;
57     for(R i = 1; i <= n; i ++)
58     {
59         while(r[q[head]] < i) ++head;//如果当前队首已经取不到了
60         int now = q[head];
61         f[i] = count(i, now);//error ??? 用函数的话会爆了会自动转换为inf?
62         last[i] = now;
63         if(count(n, q[tail]) < count(n, i)) continue;//如果最后一个都不够优，那就不二分了
64         while(count(l[q[tail]], q[tail]) > count(l[q[tail]], i)) --tail;//如果当前可以覆盖前面的整个区间
65         half(i);//注意上面的while要在调用half之前修改，这样取到的now才是正确的
66     }
67 }
68 
69 inline void write()
70 {
71     if(f[n] > inf) puts("Too hard to arrange");
72     else
73     {
74         printf("%lld
", (LL)(f[n] + 0.5));//注意精度误差
75         for(R i = n; i; i = last[i]) Next[last[i]] = i;
76         int now = 0;
77         for(R i = 1; i <= n; i ++)
78         {
79             now = Next[now];//now先跳了吧
80             int be = now;//先只到这行结尾，因为for还要加的
81             for(R j = i; j < be; j ++) printf("%s ", ss[j] + 1);
82             printf("%s
", ss[be] + 1), i = be;//最后再赋i,因为for中还要用到当前i
83         }
84     }
85     puts("--------------------");
86 }
87 
88 int main()
89 {
90     scanf("%d", &t);
91     while(t--) pre(), getans(), write();
92     return 0;
93 }

View Code

　2，分治

　　假设我们当前的被决策区间是[l, r], 决策点区间是[ll, rr],那么我们取被决策区间的中点mid = (l + r) >> 1,然后在[ll, rr]中暴力寻找mid的最优决策点k，于是根据决策单调性，我们有：

　　被决策区间[l, mid - 1]对应的决策点区间是[ll, k].同理，被决策区间[mid + 1, r]对应的决策点区间是[k, rr],于是我们就将这个区间划分为了2半，不断向下递归减小决策点范围即可用正确的复杂度求出所有的转移。