uoj104(wqs二分+斜率优化)

|

题目链接

http://uoj.ac/problem/104

题解

主要学习 $wqs$ 二分求解时的方案输出，处理起来还是比较麻烦的。。

当二分到需要的权值时，用这个权值再做一次 $DP$ ，并记录所有转移路径，并维护转移到当前点所需要经过的最少的边和最多的边，然后从后往前搜，当当前需要的转移数加在两个最值之间，这个一定可以作为一个转移点，那么直接选择这个转移点往下搜就可以了。。

这个算法唯一的问题就是转移的边可能会很多。。但是想把这个卡 T 这个数据实在是不太好造(至少窝觉得这对出题人来说是个非常有挑战性的构造题)，所以窝萌就把他忽略了吧。。

有个细节是，当窝在二分时将 转移次数 $\ge k$ 作为二分判断条件时会在边界求解不出真正的解，这是因为在 $DP$ 的时候窝优先取前面的决策点(因为窝还要将后面的决策点保留到队列中以记录转移路径)。因此在遇到边界条件(凸包上平的那一段)窝会优先选择区间划分数较小的一段，所以如果当用 转移次数 $\ge k$ 时除非转移次数等于 $k$ 否则该权值下没有窝萌需要的答案。




代码

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define mid (x+y>>1)
#define eps 1e-8
#define succ(x) (1ll<<(x))
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define NM 100005
#define nm 10005
using namespace std;
const double pi=acos(-1);
const int inf=998244353;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}


int n,m;
ll d[NM],ans,a[NM];
int p[NM],q[NM],qh,qt,mmax[NM],mmin[NM],c[NM];
vector<int>pre[NM];

double slope(int x,int y){
    if(a[x]==a[y])return d[x]>d[y]?inf:-inf;
    return 1.0*(d[x]-d[y])/(a[y]-a[x])+a[x]+a[y];
}

bool check(ll t){
    q[qh=qt=0]=0;
    inc(i,1,n){
	while(qh<qt&&slope(q[qh],q[qh+1])<a[i])qh++;
	d[i]=d[q[qh]]+(a[i]-a[q[qh]])*a[q[qh]]-t;
	p[i]=p[q[qh]]+1;
	while(qh<qt&&slope(q[qt-1],q[qt])>slope(q[qt],i))qt--;
	q[++qt]=i;
    }
    return p[n]<=m+1;
}
void _check(ll _t){
    q[qh=qt=0]=0;
    inc(i,1,n){
	while(qh<qt&&slope(q[qh],q[qh+1])<a[i])qh++;
	d[i]=d[q[qh]]+(a[i]-a[q[qh]])*a[q[qh]]-_t;
	mmin[i]=n+1;
	for(int k=qh,t=q[qh];k<=qt&&d[i]+_t==d[t]+(a[i]-a[t])*a[t];t=q[++k]){
	    pre[i].push_back(t);
	    mmax[i]=max(mmax[i],mmax[t]+1);
	    mmin[i]=min(mmin[i],mmin[t]+1);
	}
	while(qh<qt&&slope(q[qt-1],q[qt])>slope(q[qt],i))qt--;
	q[++qt]=i;
    }
    printf("%lld\n",d[n]+ans*(m+1));
    for(int x=n,t=m;t;){
	for(auto&j:pre[x])if(mmin[j]<=t&&t<=mmax[j]){
	    x=c[t]=j;
	    t--;
	    break;
	}
    }
}

int main(){
    n=read();m=read();
    inc(i,1,n)a[i]=read()+a[i-1];
    for(ll x=0,y=a[n]*a[n];x<=y;)
	if(check(mid)){//<=k
	    ans=mid;y=mid-1;
	}else x=mid+1;
    _check(ans);
    inc(i,1,m)printf("%d%c",c[i]," \n"[i==m]);
    return 0;
}