简短题解集合

 1 #include <cmath>
 2 #include <queue>
 3 #include <vector>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <algorithm>
 7 #define N1 1010000
 8 #define N2 4201
 9 #define M1 120
10 #define ll long long
11 #define dd double  
12 #define uint unsigned int
13 #define idx(X) (X-‘0‘)
14 using namespace std;
15 
16 ll gll()
17 {
18     ll ret=0;int fh=1;char c=getchar();
19     while(c<‘0‘||c>‘9‘){if(c==‘-‘)fh=-1;c=getchar();}
20     while(c>=‘0‘&&c<=‘9‘){ret=ret*10+c-‘0‘;c=getchar();}
21     return ret*fh;
22 }
23 int n;
24 ll D[N1],p[N1],c[N1],f[N1];
25 ll x[N1],y[N1];
26 ll sp[N1],sdp[N1];
27 int que[N1];
28 
29 int main()
30 {
31     //freopen("t2.in","r",stdin);
32     scanf("%d",&n);
33     for(int i=1;i<=n;i++)
34     {
35         D[i]=gll(),p[i]=gll(),c[i]=gll();
36         sp[i]=sp[i-1]+p[i];
37         sdp[i]=sdp[i-1]+1ll*p[i]*D[i];
38     }
39     int hd=1,tl=0,j;
40     que[++tl]=0;
41     for(int i=1;i<=n;i++)
42     {
43         while(hd+1<=tl&&(y[que[hd+1]]-y[que[hd]])<=(x[que[hd+1]]-x[que[hd]])*D[i])
44             hd++;
45         j=que[hd];
46         f[i]=f[j]+ D[i]*sp[i]-D[i]*sp[j] -sdp[i]+sdp[j] +c[i];
47         x[i]=sp[i],y[i]=f[i]+sdp[i];
48         while(hd+1<=tl&&(y[que[tl]]-y[que[tl-1]])*(x[i]-x[que[tl-1]])>=(y[i]-y[que[tl-1]])*(x[que[tl]]-x[que[tl-1]]))
49             tl--;
50         que[++tl]=i;
51     }
52     printf("%lld\n",f[n]);
53     return 0;
54 }