CF321E Ciel and Gondolas / BZOJ5311 贞鱼

发表于 | 评论数： | 阅读次数：
本文字数： 4.3k | 阅读时长 ≈ 4 分钟

CF321E Ciel and Gondolas / BZOJ5311 贞鱼

传送门

洛谷
BZOJ

题意描述

众所周知，贞鱼是一种高智商水生动物。不过他们到了陆地上智商会减半。
这不？他们遇到了大麻烦！
$n$只贞鱼到陆地上乘车，现在有$k$辆汽车可以租用。
由于贞鱼们并不能在陆地上自由行走，一辆车只能载一段连续的贞鱼。
贞鱼们互相有着深深的怨念，每一对贞鱼之间有怨气值。
第$i$只贞鱼与第$j$只贞鱼的怨气值记为$Y _ {i,j}$，且$Y _ {i,j}$=$Y _ {j,i}$，$Y _ {i,i}$=0。
每辆车载重不限，但是每一对在同辆车中的贞鱼都会产生怨气值。
当然,超级贞鱼zzp长者希望怨气值的总和最小。
不过他智商已经减半,想不出分配方案。
他现在找到了你,请你帮助他分配贞鱼们,并输出最小怨气值之和$ans$。

输入输出格式

输入格式：

第一行两个整数:$n$,$k$。
接下来读入一个$n$行$n$列的矩阵。矩阵中第$i$行$j$列的元素表示$Y _ {i,j}$。
当然这个矩阵是对称的。

输出格式：

一个整数$ans$，表示：最小的怨气值之和
★注意：同辆车中，贞鱼$i$,$j$之间的怨气只算一次！
$1 \le n \le 4000 ，1 \le k \le min(n , 800) , 0 \le Y _ {i,j} \le 10 $

输入输出样例

输入样例#1：

8 3
0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0

输出样例#1：

7

说明

【样例解释1】

编号为1，2，3的贞鱼一辆车：怨气值和为3；
编号为4，5，6的贞鱼一辆车：怨气值和为3；
编号为7，8的贞鱼一辆车：怨气值和为1。
最小怨气值总和为 3 + 3 + 1 = 7 。

分析

本题也是$WQS$二分的模板题，但困扰本蒟蒻的不是$WQS$二分，而是$DP$，众所周知，本题的状态转移方程式为

其中$f_i$为考虑到第$i$只贞鱼，$sum _ {i,j}$表示矩阵$(1,1),(i,1),(1,j),(i,j)$之和。
据说这个式子满足决策单调性。
决策单调性是什么？？？
就是说如果存在$f_a$比$f_b$小，那么就不可能从$f_a$转移过来。
为什么？？？
上网找了很多题解，要么不会证，要么强到不想证（菜是原罪）
终于…
发现一位巨佬——T_Y_P_E。
蒟蒻在Ta的博客里找到了证明和做法，以下转自T_Y_P_E的题解。

选择单调性的话，是和dp值的增长率的大小有关的。如果不懂的话，可以看一下下面这个图。
首先将式子中的对于i而言的非常数项提出来：-(sum[i][j]+sum[j][i]-sum[j][j])，然后下面的图表现的是括号里面(先令作F(i,j))的几何意义。

j1<j2是显然的.其中橙色部分v表示的就是F(i,j2)随i的变化量，而绿色部分就是F(i,j1)随i的变化量。可见delta(F(i,j2))是大于delta(F(i,j1))的，也就是说dp是中和sum[][]有关的那一坨中中，如果j1<j2，因为对于j1和j2而言，sum[i][i]的增加率肯定是相等的，而F(i,j1)增加的要慢一些，也就是它阻碍sum[i][i]增加的作用要小一些，那么对应的j1的总的增加量就要大一些。

因为我们要求的是最小值，而此时如果dp[j1]还大于dp[j2]的话，在i增大的过程中，j1是绝对不可能成为决策点的。于是就可以把j1舍去了。

这里博主可能说的有些复杂，能理解就好。

这样子就可以利用决策单调性把整体时间复杂度优化到O(nlognlogmaxval)了。
至于决策单调性的具体过程，大概就是先发现一个决策点对一个连续的区间进行转移，所以可以在队列里面放入一个决策点当前能够更新的左右端点和自己的下标。

首先先默认能够更新到n，然后在之后的插入决策点的过程中，将绝对不可能进行之后的转移的点弹掉，然后在一个完整的区间内部进行二分，将这个区间拆成两个，其中右边的那个就是新插进去的决策点的更新区间啦。

若您认为转载效果不佳，可在下方找到原博客网址。

学习完巨佬的优化后，本题就可以做了。
但本蒟蒻还想转一下巨佬的提示。

1.在最后算答案加回多算的代价的时候，记得是每辆车多算的代价乘上k，而不是乘上你这个方案的车的数量
2.在DP的转移过程中，除了要将值的大小设为第一比较关键字外，还要将选取车的数量设为第二关键字进行比较。通常是这样的：如果你在外层的二分中是判定当前选取车的数量<= k的时候算答案的话，你在内层就要保证在dp值相同的情况下，尽可能地少使用车；反之亦然（全部反过来就行了）。

真是叫人半懂不懂的。
蒟蒻还要思考一下。
也许以后会再更新本蒟蒻的理解以及拓展。

参考资料

T_Y_P_E的 【Codeforces 321E / BZOJ 5311】【DP凸优化】【单调队列】贞鱼

代码

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 4010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
struct Node
{
	int l;
	int r;
	int v;
}Q[maxn];
int n,m,f[maxn],cnt[maxn],sum[maxn][maxn];
int Get(int j,int i)
{
	return f[j]+(sum[i][i]+sum[j][j]-sum[i][j]-sum[j][i])/2;
}
int cmp(int v1,int v2,int n1,int n2)
{
	if(v1<v2)return 1;
	if(v1>v2)return -1;
	if(n1<n2)return 1;
	if(n1>n2)return -1;
	return 0;
}
bool check(int v)
{
	int h=0,t=0;
	Q[t]=(Node){1,n,0};
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		while(h<=t&&Q[h].r<i)h+=1;
		int j=Q[h].v;
		cnt[i]=cnt[j]+1;
		f[i]=Get(j,i)+v;
		while(h<=t&&cmp(Get(Q[t].v,Q[t].l),Get(i,Q[t].l),cnt[Q[t].v],cnt[i])==-1)t-=1;
		if(h<=t)
		{
			int l=Q[t].l,r=Q[t].r;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(cmp(Get(i,mid),Get(Q[t].v,mid),cnt[i],cnt[Q[t].v])==1)r=mid-1;
				else l=mid+1;
			}
			Q[t].r=r;
			if(l<=n)Q[++t]=(Node){l,n,i};
		}
		else Q[++t]=(Node){i,n,i};
	}
	return cnt[n]<=m;
}
int main()
{
	read(n,m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+read<int>();
	int l=0,r=0x7fffffff;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	check(l);
	printf("%d\n",f[n]-l*m);
    return 0;
}