算法學習——決策單調性優化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\n", (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\n", 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半，不斷向下遞歸減小決策點范圍即可用正確的復雜度求出所有的轉移。

轉載于:https://www.cnblogs.com/ww3113306/p/9889295.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/249104.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/249104.shtml
英文地址，請注明出處：http://en.pswp.cn/news/249104.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！