BZOJ 3437 小P的牧场（斜率优化DP）

 

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3437

 

【题目大意】

　　n个牧场排成一行，需要在某些牧场上面建立控制站，
　　每个牧场上只能建立一个控制站，每个控制站控制的牧场
　　是它所在的牧场一直到它西边第一个控制站的所有牧场
　　它西边第一个控制站所在的牧场不被控制，如果它西边不存在控制站，
　　那么它控制西边所有的牧场，每个牧场被控制都需要一定的花费，
　　而且该花费等于它到控制它的控制站之间的牧场数目乘上该牧场的放养量，
　　在第i个牧场建立控制站的花费是ai，每个牧场i的放养量是bi，
　　求最小总花费。

 

【题解】

　　考虑只在n建立控制站的情况，答案为∑b[i]*(n-i)
　　记dp[i]为考虑了i到n的情况，并且在i点建立了控制站的最优情况，
　　有dp[i]=max{dp[j]+sum[i]*(j-i)}-a[i]
　　=-a[i]-sum[i]*i+max(dp[j]+sum[i]*j)
　　为关于sum[i]的线性函数，那么对f(y)=x*y+dp[x]进行斜率优化

　　正向思路（by安琪）：

          

 

 

【代码】

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1000010;
int deq[N],n;
LL tot,ans,dp[N],S[N],a[N],b[N];
LL f(int x,LL y){return y*x+dp[x];}
bool check(int f1,int f2,int f3){
    LL a1=f1,b1=dp[f1];
    LL a2=f2,b2=dp[f2];
    LL a3=f3,b3=dp[f3];
    return (a2-a1)*(b3-b2)<=(b2-b1)*(a3-a2);
}
void solve(){
    for(int i=1;i<=n;i++)S[i]=S[i-1]+b[i];
    int s=0,t=1;
    deq[0]=n;
    for(int i=n-1;i;i--){
        while(s+1<t&&f(deq[s],S[i])<=f(deq[s+1],S[i]))s++;
        dp[i]=-a[i]-S[i]*i+f(deq[s],S[i]);
        ans=max(ans,dp[i]); 
        while(s+1<t&&check(deq[t-2],deq[t-1],i))t--;
        deq[t++]=i;
    }printf("%lld\n",tot-ans);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
    for(int i=1;i<n;i++)tot+=b[i]*(n-i);
    tot+=a[n]; solve();
    return 0;
}