BZOJ4409 [Usaco2016 Feb]Circular barn 动态规划斜率优化

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

原文链接http://www.cnblogs.com/zhouzhendong/p/8724739.html

题目传送门 - BZOJ4409

题意

有一个N个点的环，相邻两个点距离是1。点顺时针标号为1..N。最初每一个点是空的。要求最终点i存在ri头牛。你有∑ri头牛。你可以选择最多k个点，然后把你的牛任意分配在这k个点里。之后，每一头牛可以选择不动，也可以顺时针走d格并呆在那里。这样，它要耗费d的能量。通过合理选择点、合理分配牛、合理安排牛的走动，使得消耗的总能量最小。

$n\leq 1000,k\leq 7,r_i\leq 10^6$

题解

首先，我们来说一个比较simple的结论。

原始分配方案的一个点的牛不可能走到下一个点。

很显然，如果可以走到下一个点，那么直接分配在下一个点更优。

于是我们发现这就是分段贡献。

考虑先断环为链，所以我们先用掉一层循环，来枚举环的开头。（事实上我是通过顺时针旋转数列实现的）

然后考虑到剩下的部分，是个DP。

很容易写出方程：（为了方便，这里的$a_i$即题目描述的$r_i$）

$$dp_{r,i}=min\{dp_{r-1,j}+\sum_{k=j+1}^i (k-j-1)a_k\}\ \ \ (0\leq j<i)$$

然后就是经典的斜率优化套路了。

关于DP的斜率优化看这里$\longrightarrow$传送门。

可以参照下面两道题的做法，这里我不再赘述了。

BZOJ1096

BZOJ3675

然后注意一下初始的时候的$dp_{0,i}$的值为$\infty$（BZOJ3675里面求的是最大值，故初始化为0；但这里求的是最小值。）。

时间复杂度$O(n^2k)$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1005;
int n,R,q[N],head,tail;
LL a[N],sum[N],vsum[N],x[N],y[N],dp[10][N],ans=1LL<<60;
int main(){
scanf("%d%d",&n,&R);
for (int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for (int _i_=1;_i_<=n;_i_++){
sum[0]=vsum[0]=0;
for (int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i],vsum[i]=vsum[i-1]+a[i]*(i-1);
for (int i=1;i<=n;i++)
dp[0][i]=1LL<<45;
dp[0][0]=0;
for (int r=1;r<=R;r++){
for (int i=0;i<=n;i++)
x[i]=i,y[i]=dp[r-1][i]-vsum[i]+sum[i]*i;
head=1,tail=0;
q[++tail]=0;
for (int i=1;i<=n;i++){
int j=q[head+1],k=q[head];
while (tail-head>0&&y[j]-y[k]<=sum[i]*(x[j]-x[k]))
head++,j=q[head+1],k=q[head];
j=k;
dp[r][i]=dp[r-1][j]+vsum[i]-vsum[j]-(sum[i]-sum[j])*j;
j=q[tail],k=q[tail-1];
while (tail-head>0&&(y[i]-y[j])*(x[j]-x[k])<=(y[j]-y[k])*(x[i]-x[j]))
tail--,j=q[tail],k=q[tail-1];
q[++tail]=i;
}
ans=min(ans,dp[r][n]);
}
for (int i=1;i<=n;i++)
a[i-1]=a[i];
a[n]=a[0];
}
printf("%lld",ans);
return 0;
}