C++(g++ 7.5.0) 解法, 执行用时: 442ms, 内存消耗: 48120K, 提交时间: 2022-09-05 19:27:30
#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
#include<set>
#include<map>
#include<stack>
#include<algorithm>
#include<sstream>
#include<math.h>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define dream return 0;
ll x[1000005], p[1000005], c[1000005];//和第一个工厂的距离,产品数量,建设产库的数量
ll dp[1000005];//建设仓库的价格
ll sum1[1000005], sum2[1000005];
ll q[1000005];
ll tt, hh;
void solve()
{
ll n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> p[i] >> c[i];
}
for (int i = 1; i <= n; i++)
{
sum1[i] = sum1[i - 1] + p[i];
sum2[i] = sum2[i - 1] + x[i] * p[i];
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i = 1; i <= n; i++)
{
/*for (int j = 0; j < i; j++)
{
/*ll sum = 0;
for (int k = j + 1; k <= i; k++)
{
sum += (x[i] - x[k])*p[k];
}*/
//x[i] * p[k] - x[k] * p[k];
//dp[i] = min(dp[i], dp[j] + x[i] * (sum1[i] - sum1[j]) - (sum2[i] - sum2[j]) + c[i]);
while (hh < tt && (dp[q[hh + 1]] +sum2[q[hh+1]]- dp[q[hh]]-sum2[q[hh]]) <= x[i] * (sum1[q[hh + 1]] - sum1[q[hh]]))
{
hh++;
}
ll j = q[hh];
dp[i]= dp[j] + x[i] * (sum1[i] - sum1[j]) - (sum2[i] - sum2[j]) + c[i];
while (hh < tt && (dp[q[tt]] - dp[q[tt - 1]]+sum2[q[tt]]-sum2[q[tt-1]])*(sum1[i]-sum1[q[tt]]) >= (dp[i]-dp[q[tt]]+sum2[i]-sum2[q[tt]])*(sum1[q[tt]]-sum1[q[tt-1]]))
{
tt--;
}
q[++tt] = i;
}
//(dp[i]+sum2[i]-c[i]-x[i]*sum1[i])+x[i]*sum1[j]=dp[j]+sum2[j]
//b + k * x = y;
//k=x[i];
//y=dp[j]+sum2[j];
//x=sum1[j];
long long ans = 0x3f3f3f3f3f3f;
for (int i = n; i >= 1; i--)
{
ans = min(ans, dp[i]);
if (p[i])break;
}
printf("%lld\n", ans);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
dream;
}
C++(clang++11) 解法, 执行用时: 354ms, 内存消耗: 24136K, 提交时间: 2020-10-21 14:58:18
#include<bits/stdc++.h>
#define k(i,j) 1.0*(f[j]-f[i])/(p[j]-p[i])
using namespace std;
const int nn=1001021;
int n,t,tt,x[nn],c[nn],q[nn];
long long ans,p[nn],f[nn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%lld%d",x+i,p+i,c+i);
for(int i=1;i<=n;i++)
f[0]+=p[i]*(x[n]-x[i]),p[i]+=p[i-1];
ans=(f[0]+=c[n]);
for(int i=1,j;i<n;i++){
if(t>=tt)t=tt;
else while(t<tt&&k(q[t],q[t+1])<x[i]-x[n])t++;
j=q[t],f[i]=f[j]-(p[i]-p[j])*(x[n]-x[i])+c[i];
for(;tt&&k(q[tt-1],q[tt])>=k(q[tt-1],i);tt--);
ans=min(ans,f[q[++tt]=i]);
}return printf("%lld",ans),0;
}
，保证
