study from:
https://www.cnblogs.com/flashhu/p/9480669.html
3.斜率dp
study from:http://www.cnblogs.com/MashiroSky/p/6009685.html
或单减
https://www.luogu.org/problemnew/show/P3195
study from:http://www.cnblogs.com/MashiroSky/p/5968118.html
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cmath>
4 #include <cstring>
5 #include <time.h>
6 #include <string>
7 #include <set>
8 #include <map>
9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <ext/rope>
15 #include <algorithm>
16 #include <iostream>
17 using namespace std;
18 #define ll long long
19 #define minv 1e-6
20 #define inf 1e9
21 #define pi 3.1415926536
22 #define E 2.7182818284
23 const ll mod=1e9+7;//998244353
24 const int maxn=5e4+10;
25
26 ll sum[maxn],a[maxn],f[maxn],L;
27 int q[maxn];
28
29 double slope(int j,int k)
30 {
31 return (f[k]-f[j]+(a[k]+L+1)*(a[k]+L+1)-(a[j]+L+1)*(a[j]+L+1))
32 /2.0/(a[k]-a[j]);
33 }
34
35 int main()
36 {
37 int n,l,r,i;
38 ll s;
39 scanf("%d%lld",&n,&L);
40 sum[0]=0;
41 l=1,r=1;
42 f[0]=0;
43 q[1]=0;
44 for (i=1;i<=n;i++)
45 {
46 scanf("%lld",&s);
47 sum[i]=sum[i-1]+s;
48 a[i]=sum[i]+i;
49 while (r>l && slope(q[l],q[l+1])<=a[i]) //have =
50 l++;
51 f[i]=f[q[l]]+pow(i-q[l]-1+sum[i]-sum[q[l]]-L,2);
52 while (r>l && slope(q[r-1],q[r])>slope(q[r],i))//have no =
53 r--;
54 q[++r]=i;
55 }
56 printf("%lld",f[n]);
57 return 0;
58 }
https://www.luogu.org/problemnew/show/P2900
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cmath>
4 #include <cstring>
5 #include <time.h>
6 #include <string>
7 #include <set>
8 #include <map>
9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <ext/rope>
15 #include <algorithm>
16 #include <iostream>
17 using namespace std;
18 #define ll long long
19 #define minv 1e-6
20 #define inf 1e9
21 #define pi 3.1415926536
22 #define nl 2.7182818284
23 const ll mod=1e9+7;//998244353
24 const int maxn=5e4+10;
25
26 struct node
27 {
28 ll x,y;
29 }s[maxn],d[maxn];
30
31 ll f[maxn];
32 int q[maxn];
33
34 int cmp(node a,node b)
35 {
36 if (a.y==b.y)
37 return a.x>b.x;
38 else
39 return a.y>b.y;
40 }
41
42 double slope(int j,int k)
43 {
44 return 1.0*(f[k]-f[j])/(d[j+1].y-d[k+1].y);
45 }
46
47 int main()
48 {
49 int n,i,m,k,l,r;
50 scanf("%d",&n);
51 for (i=1;i<=n;i++)
52 scanf("%lld%lld",&s[i].x,&s[i].y);
53 sort(s+1,s+n+1,cmp);
54 m=0;
55 k=0;
56 for (i=1;i<=n;i++)
57 if (s[i].x>k)
58 {
59 d[++m]=s[i];
60 k=s[i].x;
61 }
62
63 f[0]=0;
64 q[1]=0;
65 l=1,r=1;
66 for (i=1;i<=m;i++)
67 {
68 while (l<r && slope(q[l],q[l+1])<=d[i].x)
69 l++;
70 f[i]=f[q[l]]+d[q[l]+1].y*d[i].x;
71 while (l<r && slope(q[r-1],q[r])>slope(q[r],i))
72 r--;
73 q[++r]=i;
74 }
75 printf("%lld",f[m]);
76 return 0;77 }