Fork me on GitHub

「BZOJ5311 / CF321E」 贞鱼 WQS二分+决策单调优化 DP

发表于 | 分类于 ，
字数统计: 820字 | 阅读时长 ≈ 4分钟

当决策单调与WQS二分结合.

Links there:CF321E bzoj5311

题意

给 $n$ 条贞鱼与每对贞鱼之间的怨气值 求分成 $K$ 段,每段的怨气值之和的最小值.

$1 \leq n \leq 4000, 1 \leq k \leq min(n,800)$

思路

先想朴素的 $dp$.不难想到这个 $O(n^2k)$ 的转移

其中 $calc(i,j)$ 利用前缀和做一下就好了.显然跑不过去.

类似 $JSOI2011 Lemon$ ,假设有 $k < j \leq i$ ,我们发现如果有 $j$ 在某个时刻比 $k$ 优秀那么它永远比 $k$ 优秀.因为$f[j] + calc(j,i) > f[k] + calc(k,i)$ , $f[j] - f[k] > calc(k,i) - calc(j,i) > 0$

但是不能斜率优化 因为右边的式子在换了决策点之后 并不一定单调.

搞一个单调队列 又是类似 $JSOI2011 Lemon$ ,保证更优秀的答案出现的时间单调 每次二分去找.

然后我们成功优化到了 $O(nlognk)$

发现还是过不去 为什么呢

读入太大了

再考虑一个优化 观察到这里的限制是恰好 $K$ 段

用 $WQS$ 二分的套路 每次选一段的时候加一个怨气值 记录最后选了几段.

发现如果这个附加怨气值越小的话对于固定的 $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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//Keep pluggin',this is your only outlet.
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cctype>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
    return *S++;
}
inline int read(void){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=gc();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return x * f;
}
const int MAXN = 4e3 + 100;
int n,a[MAXN][MAXN],m,pre[MAXN][MAXN];
int f[MAXN],c[MAXN],q[MAXN];
inline int calc(int x,int y){
    return f[x] + ((pre[y][y] - pre[x][y] - pre[y][x] + pre[x][x]) >> 1);
}
inline int isbetter(int x,int y,int t){
    int w1 = calc(x,t),w2 = calc(y,t);
    if (w1 > w2) return 1;
    if (w2 > w1) return 0;
    return (c[x] >= c[y]);
}
inline int Tim(int x,int y){ //the pos decision x is better than y
    int l = y + 1,r = n,mid;
    while(l <= r) {
        mid = (l + r) >> 1;
        if (isbetter(x,y,mid)) r = mid - 1;
        else l = mid + 1;
    }
    return r + 1; // +1 is the valid place.
}
inline int isok(int mid){
    int head = 1,tail = 1;
    q[head] = 0;
    for (int i = 1; i <= n; ++i) {
        while(head < tail && isbetter(q[head],q[head+1],i)) ++head;
        f[i] = calc(q[head],i) + mid;
        c[i] = c[q[head]] + 1;
        while(head < tail && Tim(q[tail-1],q[tail]) > Tim(q[tail],i)) --tail;
        q[++tail] = i;
    }
    return c[n] <= m;
}
///------------------head------------------
signed main(signed argc, char *argv[]){
    n = read(),m = read();
    int ans = 0;
    rep(i,1,n)
        rep(j,1,n) {
            a[i][j] = read();
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]; //prefix sum
        }
    int L = 0,R = pre[n][n] >> 1;
    while(L <= R) {
        // printf("%lld %lld\n",L,R);
        int mid = (L+R) >> 1;
        // printf("%lld\n",mid);
        if (isok(mid)) {ans = f[n] - mid * m; R = mid - 1;}
        else L = mid + 1;
    }
    printf("%d\n",ans);
    return 0;
}

/* Examples: */
/*

*/

/*

*/