OI - Ciel and Gondolas

某 OJ 把这道题搬去做了 5311……名叫贞鱼(=_=)


Part1. 题面

有 n 个人和 k 辆车。人们排队上车,所以每辆车内是连续的一段人。已知第 i 个人和第 j 个人的厌恶值为 $y_{i,j}$,厌恶是相互的,即 $y_{i,j}=y_{j,i}$。

如果 i 和 j 在同一辆车里,就会产生 $y_{i,j}$ 的不愉快值($y_{i,j}$ 和 $y_{j,i}$ 只计算一次)。

数据结构:$1\le n\le4000,0\le y_{i,j}\le 9$,满足 $y_{i,j}=y_{j,i},y_{i,i}=0$。


Part2. 解析

Part2/1. 凸优化

发现是恰好 $k$ 辆车,(需要足够的脑洞)根据这一点可以向凸优化这方面思考。
显然车越多、总不愉快值越小,大概可以发现 $f(x)$ 表示 $n$ 个人有 $x$ 辆车时的最优解,$\left(x,f(x)\right)$ 成凸包。于是凸优化是正确的。

那么就是要二分斜率 $c$,求 $f’(x)=f(x)+cx$ 的最小值。即考虑每分一辆车,代价就额外增加 $c$。

根据这些,我们就不用管“恰好 $k$ 辆车”的限制,可以设计出 DP 状态 dp[x],表示前 x 个人划分完毕的最小总不愉快值,再维护 cnt[x] 为当 dp[x] 取得最小值时,最少 分了多少辆车(你也可以维护 最大,反正一定要知道自己是求的最大还是最小,不能随便)。

然后就可以得到一个非常显然的转移式子,也就是把第 j+1 到 i 个人分到一个车子里面,还要加上每辆车的附加值 c:

1
dp[i] = min{ dp[j] + (sum[i][i] - sum[i][j] - sum[j][i] + sum[j][j])/2 + c }

> Tip
sum[a][b] 是 $\sum_{i=1}^a\sum_{j=1}^by_{i,j}$。

转移的时候还要统计一下 cnt[i]。最后根据 cnt[n] 和 $k$ 的大小,更改 $c$ 的取值范围。

Part2/2. 决策单调性

然而我们发现,上面那种转移,对于每个 i,要枚举 j,也就是 $O(n^2)$ 的…… 然后再套上带权二分的 $O(\log_2w)$,变成了 $O(n^2\log_2w)$,好像卡不过 BZOJ 的机子(=_=)。

再观察 DP 结果(其实我是听 tiw dalao 讲的),可以发现 DP 决策是有单调性的!也就是说 dp[i]最优转移点 $d(i)$ 是与 $i$ 呈现非递减 关系的。所以再用决策单调性优化一下,就将枚举 j 的 $O(n)$ 降至二分 维护决策队列的 $O(\log_2n)$。

此时复杂度为 $O(n\log_2n\log_2w)$ 可以接受。

> Tip

关于决策单调性,比如下面这样:

1
2
i    =  1  2  3  4  ...
d(i) = 0 1 1 2 ...

其中 d(i) 是 i 的最优转移点,对于这道题也就是说 dp[i] 的最小值为:
dp[i] = dp[d(i)]+(sum[i][i]-sum[d(i)][i]-sum[i][d(i)]+sum[d(i)][d(i)])/2+c

具体实现是用队列,存储对于每一个 i,哪一段区间是以它为最优决策点(可能为空)。当我们计算出 dp[i],因为决策具有单调性,就可以二分 i 的最左边的最优决策点。

具体看代码吧。


Part3. 源代码

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
/*Lucky_Glass*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=4000;

int n,m;
int sum[N+3][N+3],cnt[N+3];
long long dp[N+3];
int que[N+3],inc[N+3],lef,rig;

int AddUp(int x1,int y1,int x2,int y2){return sum[x1][y1]-sum[x1][y2]-sum[x2][y1]+sum[x2][y2];}
bool cmp(int las,int now,int finc){
long long resu_las=dp[las]+AddUp(finc,finc,las,las)/2,
resu_now=dp[now]+AddUp(finc,finc,now,now)/2;
int cnt_las=cnt[las]+1,
cnt_now=cnt[now]+1;
return resu_now<resu_las || (resu_now==resu_las && cnt_now<cnt_las);
}
/*
> Hint.
if cmp() return 0
now is better than las
*/

int BinarySearch(int incl,int incr,int lasque,int now){
int las=que[lasque];
if(!cmp(las,now,incr)) return 0;
if(cmp(las,now,incl)){
rig=lasque;
que[rig]=now;
inc[rig]=n;
return 1;
}
while(incl+1<incr){
int incm=(incl+incr)>>1;
if(cmp(las,now,incm)) incr=incm;
else incl=incm;
}
rig=lasque+1;
inc[rig]=n;
que[rig]=now;
inc[lasque]=incr-1;
return 2;
}
/*
> Hint.
if BinarySearch() return:
0: las is always better than now
1: now is always better than las
2: ...
*/
bool Check(int add){
for(int i=1;i<=n;i++) dp[i]=(1ll<<60),cnt[i]=1e9;
dp[0]=0;
que[lef=rig=1]=0;inc[1]=n;
for(int i=1;i<=n;i++){
while(inc[lef]<i) lef++;
int j=que[lef];
if(i==inc[lef]) lef++;
long long fdp=dp[j]+AddUp(i,i,j,j)/2+add;
dp[i]=fdp;
cnt[i]=cnt[j]+1;
for(int j=rig;j>=lef;j--){
int resu=BinarySearch((j==lef? i+1:inc[j-1]+1),inc[j],j,i);
if(resu==2 || resu==0) break;
}
}
return cnt[n]<=m;
}
#define gc if(++ip==ie)fread(ip=buf,1,SZ,stdin)
const int SZ=1<<19;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int gi(){
gc;while(*ip<'-')gc;
bool f=*ip=='-';if(f)gc;
int x=*ip&15;gc;
while(*ip>'-'){x*=10;x+=*ip&15;gc;}
return f?-x:x;
}
int main(){
n=gi();m=gi();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
sum[i][j]=gi();
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
int adl=-1e9,adr=1e9;
while(adl+1<adr){
int adm=floor(adl/2.0+adr/2.0);
if(Check(adm)) adr=adm;
else adl=adm;
// printf("? %d -> %d\n",adm,cnt[n]);
}
Check(adr);
printf("%lld\n",dp[n]-1ll*adr*m);
return 0;
}

The End

Thanks for reading!

BZOJ什么破机子……

0%