建造记者站[jzoj4646]

发表于 分类于

题意

题面

$n\leq 20000,m\leq 100$

题解

算法一

考虑DP，设 $f_{k,i}$ 表示选了 $k$ 个记者站时，考虑了前 $i$ 个村庄，第 $i$ 个村庄上有一个记者站的最小花费。

那么有DP式子：$f_{k,i}=\min_{1\le j <i}(f_{k-1,j}+c_i+g_{j,i})$

其中 $g_{j,i}$ 表示，$[j,i]$ 内只有 $i,j$ 两个点被选时，不能被覆盖的点的 $P$ 值的和。

暴力预处理 $g_{l,r}$，暴力计算 $f_{k,i}$，时间复杂度 $O(n^3+n^2m)$，得分30分。

算法二

盲猜 $g$ 满足四边形不等式，打表验证。

反正最后发现这个DP有决策单调性。

由于 $f$ 的计算和前面的DP值无关，因此考虑分治。

现在的问题转换成如何计算一个 $f_{k,i}$。也就是如果计算 $g_{j,i}$。

不能被覆盖的点 $k$ 当且仅当 $d_j<d_k-r_k,d_k+r_k<d_i$。

于是变成一个三位偏序问题，可用树套树在线解决。

时间复杂度 $O(nm\log^2n)$，常数极大，应该可以有 $70+$ 的样子。

算法三

考虑直接DP做，随着 $i$ 的增加，维护 $f_{k-1,j}+g_{j,i}(1\le j <i)$ 的最小值。

当 $i+1$ 时考虑哪些 $g_{j,i}$ 会变化，如果此时有新的 $d_k+r_k<d_i$ 出现，那么所有满足 $d_j<d_k-r_k$ 的 $j$ 的 $g_{j,i}$ 就会加上 $p_k$。

于是对于每个 $k$，预处理出最大的 $j$ 满足 $d_j<d_k-r_k$ ，记为 $l_k$。然后维护一个堆，DP时每次取出最小的 $d_k+r_k$，判断是否满足条件。如果是，则将 $[1,l_k]$ 的值全部加上 $p_k$ 即可。

用线段树维护区间加区间最值。

时间复杂度 $O(nm\log n)$。

程序

这里写的是算法三的。

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=20010;
const int inf=0x3f3f3f3f;
namespace SGT{
	int mi[N<<2],tag[N<<2];
	#define lc (u<<1)
	#define rc (u<<1|1)
	#define ls lc,l,mid
	#define rs rc,mid+1,r
	int *g;
	void build(int u,int l,int r)
	{
		tag[u]=0;
		if(l==r)
		{
			mi[u]=g[l];
			return;
		}
		int mid=l+r>>1;
		build(ls); build(rs);
		mi[u]=min(mi[lc],mi[rc]);
	}
	void init(int n,int *f)
	{
		g=f; build(1,1,n);
	}
	inline void pushtag(int u,int t)
	{
		tag[u]+=t; mi[u]+=t;
	}
	inline void pushdown(int u)
	{
		if(!tag[u]) return;
		pushtag(lc,tag[u]); pushtag(rc,tag[u]);
		tag[u]=0;
	}
	void add(int u,int l,int r,int L,int R,int x)
	{
		if(L>R) return;
		if(L<=l&&r<=R) return pushtag(u,x);
		int mid=l+r>>1;
		pushdown(u);
		if(L<=mid) add(ls,L,R,x);
		if(mid<R) add(rs,L,R,x);
		mi[u]=min(mi[lc],mi[rc]);
	}
	void update(int u,int l,int r,int p,int x)
	{
		if(l==r) return (void)(mi[u]=x,tag[u]=0);
		int mid=l+r>>1;
		pushdown(u);
		(p<=mid)?update(ls,p,x):update(rs,p,x);
		mi[u]=min(mi[lc],mi[rc]);
	}
	int ask(int u,int l,int r,int L,int R)
	{
		if(L<=l&&r<=R) return mi[u];
		pushdown(u);
		int mid=l+r>>1,ans=inf;
		if(L<=mid) ans=min(ans,ask(ls,L,R));
		if(mid<R)  ans=min(ans,ask(rs,L,R));
		return ans;
	}
}
#define CASET fo(___,1,read())
struct node{
	int id,val;
	friend inline bool operator<(const node &A,const node &B)
	{
		if(A.val==B.val) return A.id<B.id;
		return A.val<B.val;
	}
};
node u;
priority_queue<node> q;
int n,m;
int d[N],c[N],r[N],p[N],le[N];
int f[103][N];
int main()
{
	n=read(); m=min(n,read());
	fo(i,2,n) d[i]=read();
	fo(i,1,n) c[i]=read();
	fo(i,1,n) r[i]=read();
	fo(i,1,n) p[i]=read();
	fo(i,1,n) le[i]=lower_bound(d+1,d+n+1,d[i]-r[i])-d-1;
	memset(f,0x3f,sizeof(f));
	f[1][0]=0;
	fo(i,1,n)
	{
		f[1][i]=f[1][i-1];
		for(;!q.empty();)
		{
			u=q.top();
			if(-u.val<d[i]) f[1][i]+=p[u.id],q.pop();
			else break;
		}
		q.push((node){i,-d[i]-r[i]}); 
	}
	fo(i,1,n) f[1][i]+=c[i];
	fo(k,2,m)
	{
		SGT::init(n,f[k-1]);
		for(;!q.empty();q.pop());
		fo(i,1,n)
		{
			for(;!q.empty();)
			{
				u=q.top();
				if(-u.val<d[i])
					SGT::add(1,1,n,1,le[u.id],p[u.id]),q.pop();
				else break;
			}
			if(i!=1) f[k][i]=SGT::ask(1,1,n,1,i-1);
			if(f[k][i]<inf)	f[k][i]+=c[i];
			q.push((node){i,-d[i]-r[i]});
		}
	}
	int ans=0,sum;
	fo(i,1,n) ans+=p[i];
	fo(k,1,m)
	{
		for(;!q.empty();q.pop());
		sum=0;
		fd(i,n,k)
		{
			if(!q.empty())
			{
				for(;!q.empty();)
				{
					u=q.top();
					if(d[i]<u.val) sum+=p[u.id],q.pop();
					else break;
				}
			}
			q.push((node){i,d[i]-r[i]});
			ans=min(ans,sum+f[k][i]);
		}
	}
	printf("%d",ans);
	return 0;
}