学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=1096

最基础的斜率DP

我的推导&草稿：

dp[i]:i建设工厂，那么之前所有费用的最小值
朴素方程：dp[i]=min{C[i]+dp[j]+P[j+1]*dis[j+1][i]+P[j+2]*dis[j+2][i]+...+P[i]*dis[i][i]}
求dp[n]
令d[i]=dis[1][i]
dp[i]=min{C[i]+dp[j]+P[j+1]*(d[i]-d[j+1])+P[j+2]*(d[i]-d[j+2])+...+P[i]*(d[i]-d[i])}
dp[i]=min{C[i]+dp[j]+(P[j+1]+P[j+2]+...+P[i])*d[i]-P[j+1]*d[j+1]-P[j+2]*d[j+2]-...-P[i]*d[i]}
令s[i]=P[1]+...+P[i] , f[i]=P[i]*d[i]
dp[i]=min{C[i]+dp[j]+(s[i]-s[j])*d[i]-(f[j+1]+f[j+2]+...+f[i])}
令t[i]=f[1]+...+f[i]
dp[i]=min{C[i]+dp[j]+(s[i]-s[j])*d[i]-(t[i]-t[j])}
dp[i]=min{dp[j]-s[j]*d[i]+t[j]}+C[i]+s[i]*d[i]-t[i]
讨论dp[j]-s[j]*d[i]+t[j]
设j < k,j 比 k 优
dp[j]-s[j]*d[i]+t[j] < dp[k]-s[k]*d[i]+t[k]
d[i] < ((dp[k]+t[k]) - (dp[j]+t[j])) / (s[k] - s[j])
Y[k]=dp[k]+t[k]
X[k]=s[k]
d[i] < (Y[k]-Y[j]) / (X[k]-X[j])

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int getint()
{
    int r=0,k=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
    for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
    return k*r;
}
/////////////////////////////////////////////////
int n;
LL p[1000010],c[1000010];
LL d[1000010],s[1000010],t[1000010];
LL dp[1000010];
int l,r,q[1000010];
/////////////////////////////////////////////////
inline LL X(int k){return s[k];}
inline LL Y(int k){return dp[k]+t[k];}
double slope(int k,int j){return (double)(Y(k)-Y(j))/(X(k)-X(j));}
/////////////////////////////////////////////////
void input()
{
    scanf("%d",&n);
    rep(i,1,n)
    {
    	d[i]=getint(), p[i]=getint(), c[i]=getint();
    	s[i]=s[i-1]+p[i];
    	t[i]=t[i-1]+p[i]*d[i];
    }
}
void solve()
{
    rep(i,1,n)
    {
    	while(l<r&&d[i]>=slope(q[l],q[l+1]))l++;
    	int j=q[l]; dp[i]=dp[j]-s[j]*d[i]+t[j]+c[i]+s[i]*d[i]-t[i];
    	while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i))r--;
    	q[++r]=i;
    }
    cout<<dp[n]<<endl;
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("wl.out","w",stdout);
    #endif
    input(),
    solve();
    return 0;
}