BZOJ_5311_贞鱼_决策单调性+带权二分
Description
众所周知，贞鱼是一种高智商水生动物。不过他们到了陆地上智商会减半。
这不？他们遇到了大麻烦！
n只贞鱼到陆地上乘车，现在有k辆汽车可以租用。
由于贞鱼们并不能在陆地上自由行走，一辆车只能载一段连续的贞鱼。
贞鱼们互相有着深深的怨念，每一对贞鱼之间有怨气值。
第i只贞鱼与第j只贞鱼的怨气值记为Y，且Y=Y，Y=0。
每辆车载重不限，但是每一对在同辆车中的贞鱼都会产生怨气值。
当然,超级贞鱼zzp长者希望怨气值的总和最小。
不过他智商已经减半,想不出分配方案。
他现在找到了你,请你帮助他分配贞鱼们,并输出最小怨气值之和ans。
Input
第一行两个整数:n,k。
接下来读入一个n行n列的矩阵。矩阵中第i行j列的元素表示Y。
当然这个矩阵是对称的。
Output
一个整数ans，表示：最小的怨气值之和
★注意：同辆车中，贞鱼i,j之间的怨气只算一次！
1 ≤ n ≤4000 ，1 ≤ k ≤min(n , 800) , 0 ≤ Yij≤10
Sample Input
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
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
Sample Output
7
编号为1，2，3的贞鱼一辆车：怨气值和为3；
编号为4，5，6的贞鱼一辆车：怨气值和为3；
编号为7，8的贞鱼一辆车：怨气值和为1。
最小怨气值总和为 3 + 3 + 1 = 7 。
编号为1，2，3的贞鱼一辆车：怨气值和为3；
编号为4，5，6的贞鱼一辆车：怨气值和为3；
编号为7，8的贞鱼一辆车：怨气值和为1。
最小怨气值总和为 3 + 3 + 1 = 7 。
考虑二分一个权值，表示这辆车的价钱为C。
如果C=0，就会选出n辆车。
如果C=inf，就会只用一辆车。
为什么是凸的可以感性理解一下。
于是用这个权值逼近，直到选出刚好K辆车。此时选择的方案一定为最优解的一种方案。
然后考虑没有限制怎么搞。
F[i]=F[j]+(s[i][i]+s[j][j]-s[i][j]*2)/2+C。
可以证明这个转移满足决策单调性。(懒得证了)
然后直接单调队列+二分维护序列染色即可。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
int x=0; char ch=nc();
while(ch<'0'||ch>'9') ch=nc();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=nc();
return x;
}
#define N 4050
int n,K,s[N][N],f[N],g[N],C;
int Y(int j,int i) {
return f[j]+(s[j][j]+s[i][i]-s[i][j]*2)/2+C;
}
struct A {
int l,r,p;
}Q[N];
int find(const A &a,int x) {
int l=a.l,r=a.r+1;
while(l<r) {
int mid=(l+r)>>1;
if(Y(x,mid)>Y(a.p,mid)) l=mid+1;
else r=mid;
}
return l;
}
void check() {
int i;
int l=0,r=0;
f[0]=0; g[0]=0;
Q[r++]=(A){0,n,0};
for(i=1;i<=n;i++) {
while(l<r&&Q[l].r<i) l++;
f[i]=Y(Q[l].p,i); g[i]=g[Q[l].p]+1;
if(Y(i,n)<=Y(Q[r-1].p,n)) {
while(l<r&&Y(i,Q[r-1].l)<=Y(Q[r-1].p,Q[r-1].l)) r--;
if(l==r) Q[r++]=(A){i,n,i};
else {
int x=find(Q[r-1],i);
Q[r-1].r=x-1;
Q[r++]=(A){x,n,i};
}
}
}
}
int main() {
n=rd(); K=rd();
register int i,j;
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
s[i][j]=rd();
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
int l=0,r=10000;
while(l<r) {
C=(l+r)>>1;
check();
if(g[n]>K) l=C+1;
else r=C;
}
l--;
C=l; check();
printf("%d\n",f[n]-K*l);
}