Recommend 2 Blogs:
Slope optimization DP detailed explanation - Zhihu
Example 1:
P5785 [SDOI2012] task arrangement
First, we can define violence dp f [ i ] [ j ] f[i][j] f[i][j] indicates front i i i task sharing j j The set of j groups whose value is the minimum cost, we define t [ i ] t[i] t[i] is before execution i i Time prefix and required for i tasks, c [ i ] c[i] c[i] is before execution i i The cost prefix and of i tasks. For how to transfer, we can enumerate the starting point of the last group j j Component j is divided into two parts, and the first part is j − 1 j-1 Group j − 1 (corresponding to the second group) 1 − > k 1->k 1 − > k machines), the latter part is 1 1 Group 1 (corresponding to No k + 1 − > i k+1->i k+1 − > I machines), and then the state transition equation is obtained f [ i ] [ j ] = m i n ( f [ k ] [ j − 1 ] + ( j ⋅ s + ∑ a = 1 i t [ i ] ) ⋅ ( ∑ a = k + 1 i c [ i ] ) ) ， j − 1 ≤ k ≤ i f[i][j]=min(f[k][j-1]+(j\cdot s+\sum ^{i}_{a=1}t\left[ i\right])\cdot (\sum ^{i}_{a=k+1}c\left[ i\right]))，j-1\leq k\leq i f[i][j]=min(f[k][j−1]+(j⋅s+a=1∑it[i])⋅(a=k+1∑ic[i]))，j−1≤k≤i
code:
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int t[N],c[N];
int f[N][N];
int n,s;
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++){
cin>>t[i]>>c[i];
t[i]+=t[i-1];
c[i]+=c[i-1];
}
memset(f,0x3f3f3f3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=j-1;k<=i;k++)
f[i][j]=min(f[i][j],f[k][j-1]+(j*s+t[i])*(c[i]-c[k]));
int res=0x3f3f3f3f;
for(int i=1;i<=n;i++) res=min(res,f[n][i]);
cout<<res<<endl;
return 0;
}
Space complexity is
O
(
n
2
)
O(n^2)
O(n2), the time complexity is
O
(
n
3
)
O(n^3)
O(n3), T
Let's start with simplicity. Let's look at this first:
If MLE is found, you can calculate:
1
l
l
∗
5050
∗
5050
∗
4
/
1024
/
1024
=
97
M
B
>
64
M
B
1ll*5050*5050*4/1024/1024=97MB>64MB
1ll * 5050 * 5050 * 4 / 1024 / 1024 = 97mb > 64MB. We consider optimizing one dimension and get:
f
[
i
]
=
m
i
n
(
f
[
j
]
+
(
c
[
i
]
−
c
[
j
]
)
⋅
t
[
i
]
+
(
c
[
n
]
−
c
[
j
]
)
⋅
s
)
,
0
≤
j
<
i
f[i]=min(f[j]+(c[i]−c[j])\cdot t[i]+(c[n]−c[j])\cdot s),0≤j<i
f[i]=min(f[j]+(c[i]−c[j])⋅t[i]+(c[n]−c[j])⋅s),0≤j<i
c
[
i
]
c[i]
c[i] and
t
[
i
]
t[i]
t[i] is still defined as prefix and, so it is passed
code:
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int t[N],c[N];
int f[N];
int n,s;
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++){
cin>>t[i]>>c[i];
t[i]+=t[i-1];
c[i]+=c[i-1];
}
memset(f,0x3f3f3f3f,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
f[i]=min(f[i],f[j]+(c[i]-c[j])*t[i]+(c[n]-c[j])*s);
cout<<f[n]<<endl;
return 0;
}
Then further increase the range of n:
Considering the slope optimization of dp, the original formula is
f
[
i
]
=
m
i
n
(
f
[
j
]
+
(
c
[
i
]
−
c
[
j
]
)
⋅
t
[
i
]
+
(
c
[
n
]
−
c
[
j
]
)
⋅
s
)
,
0
≤
j
<
i
f[i]=min(f[j]+(c[i]−c[j])\cdot t[i]+(c[n]−c[j])\cdot s),0≤j<i
f[i]=min(f[j]+(c[i] − c[j]) t[i]+(c[n] − c[j]) s),0 ≤ J < I shift term:
f
[
i
]
=
m
i
n
(
f
[
j
]
−
(
t
[
i
]
+
s
)
⋅
c
[
j
]
+
t
[
i
]
⋅
c
[
i
]
+
s
⋅
c
[
n
]
)
,
0
≤
j
<
i
f[i]=min(f[j]-(t[i]+s)\cdot c[j]+t[i]\cdot c[i]+s\cdot c[n]),0≤j<i
f[i]=min(f[j]−(t[i]+s)⋅c[j]+t[i]⋅c[i]+s⋅c[n]),0≤j<i
requirement
f
[
i
]
f[i]
f[i]，
f
[
j
]
f[j]
f[j] and
c
[
j
]
c[j]
c[j] is two variables, then set
f
[
j
]
=
y
f[j]=y
f[j]=y，
c
[
j
]
=
x
c[j]=x
c[j]=x，
t
[
i
]
⋅
c
[
i
]
+
s
⋅
c
[
n
]
=
−
b
t[i]\cdot c[i]+s\cdot c[n]=-b
t[i] ⋅ c[i]+s ⋅ c[n] = − b, continue to deform
f
[
i
]
=
y
−
(
t
[
i
]
+
s
)
⋅
x
−
b
f[i]=y-(t[i]+s)\cdot x-b
f[i]=y−(t[i]+s)⋅x−b
Transfer:
y
=
(
t
[
i
]
+
s
)
⋅
x
+
b
y=(t[i]+s)\cdot x+b
y=(t[i]+s)⋅x+b
Observed to make
f
[
i
]
f[i]
f[i] minimum,
t
[
i
]
+
s
t[i]+s
t[i]+s is a fixed slope, so we have to
y
y
The y-axis intercept is the smallest. According to the property of the convex hull of the function, we only need to find the first minimum slope greater than the current slope, which is the point we need, and then we can do it according to the property of the monotone queue
Query (maintain convex hull):
f
q
[
t
t
]
−
f
q
[
t
t
−
1
]
c
q
[
t
t
]
−
c
q
[
t
t
−
1
]
≤
f
i
−
f
q
[
t
t
]
c
i
−
f
q
[
t
t
]
\dfrac{f_{q[tt]}-f_{q[tt-1]}}{c_{q[tt]}-c_{q[tt-1]}}\leq \dfrac{f_{i}-f_{q[tt]}}{c_{i}-f_{q[tt]}}
cq[tt]−cq[tt−1]fq[tt]−fq[tt−1]≤ci−fq[tt]fi−fq[tt]
Insert (find team head slope):
f
q
[
h
h
+
1
]
−
f
q
[
h
h
]
c
q
[
h
h
+
1
]
−
c
q
[
h
h
]
≥
t
[
i
]
+
s
\dfrac{f_{q[hh+1]}-f_{q[hh]}}{c_{q[hh+1]}-c_{q[hh]}}\geq t[i]+s
cq[hh+1]−cq[hh]fq[hh+1]−fq[hh]≥t[i]+s
code:
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n, s;
LL t[N], c[N];
LL f[N];
int q[N];
int main() {
scanf("%d%d", &n, &s);
for (int i = 1; i <= n; ++i)
scanf("%lld%lld", &t[i], &c[i]), t[i] += t[i - 1], c[i] += c[i - 1];
memset(f, 0x3f, sizeof f);
f[0] = 0;
int hh = 0, tt = 0; //Join the team f[0]
for (int i = 1; i <= n; ++i) {
//There must be at least two points in a monotone queue to form a slope
//Query (maintain convex hull):
while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) < (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) ++hh;//The slope of the team head is small. Delete it
f[i] = f[q[hh]] - (t[i] + s) * c[q[hh]] + t[i] * c[i] + s * c[n];
//Insert (find team head slope):
while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]])) --tt;
q[++tt] = i;
}
printf("%lld\n", f[n]);
return 0;
}
So you can do the problem of Luogu, but pay attention ∣ T ∣ < 2 8 \left| T\right| <2^{8} ∣ T ∣ < 28, since t t T may be a negative number, so the slope is not monotonic, so you can't just keep greater than t [ i ] + s t[i]+s t[i]+s, but the whole convex shell should be maintained. At this time, the team head is not necessarily the optimal decision. It is necessary to find a two-point search to find a position so that the slope on the left side is less than t [ i ] + s t[i]+s t[i]+s, right slope greater than t [ i ] + s t[i]+s t[i]+s
code:
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 300010;
int n, s;
LL t[N], c[N];
LL f[N];
int q[N];
int main(){
scanf("%d%d", &n, &s);
for (int i = 1; i <= n; i ++ ){
scanf("%lld%lld", &t[i], &c[i]);
t[i] += t[i - 1];
c[i] += c[i - 1];
}
int hh = 0, tt = 0;
q[0] = 0;
for (int i = 1; i <= n; i ++ ){
int l = hh, r = tt;
while (l < r){
int mid = l + r >> 1;
if (f[q[mid + 1]] - f[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]])) r = mid;
else l = mid + 1;
}
int j = q[r];
f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
while (hh < tt && (double)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (double)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt -- ;
q[ ++ tt] = i;
}
printf("%lld\n", f[n]);
return 0;
}
Example 2:
Idea:
set up
d
i
d_{i}
di indicates
i
i
The distance from kitten i to mountain 1,
s
i
s_{i}
si = corresponding to the second
i
i
i cat's keeper departure time,
t
i
t_{i}
ti ， is the second
i
i
At the end of a cat's play, first of all, you should be able to connect with the second cat
i
i
i cat, then its from
s
i
s_{i}
si ， to be met
s
i
+
d
i
>
=
t
i
s_{i}+d_{i}>=t_{i}
si+di>=ti(
d
i
d_{i}
di ， sum with prefix),
t
[
i
]
−
d
[
i
]
t[i]-d[i]
t[i] − d[i] means to receive the second
i
i
i the time when the kitten keeper should start is set as
a
[
i
]
a[i]
a[i], right
t
−
d
t - d
t − d set to after sorting
a
a
a. At this time, the problem is transformed into the minimum cost of dividing the sequence into p segments at most
f
[
i
]
[
j
]
f[i][j]
f[i][j] indicates before
i
i
i kittens, with
j
j
The minimum waiting time of j breeders has the following equation:
f
[
i
]
[
j
]
=
m
i
n
(
f
[
k
]
[
j
−
1
]
+
a
[
i
]
∗
(
i
−
k
)
−
(
s
[
i
]
−
s
[
k
]
)
f[i][j] = min(f[k][j-1] + a[i] * (i-k) - (s[i] - s[k])
f[i][j]=min(f[k][j−1]+a[i]∗(i−k)−(s[i]−s[k])
Sorting:
f
[
k
]
[
j
−
1
]
+
s
[
k
]
=
a
[
i
]
∗
k
+
f
[
i
]
[
j
]
−
a
[
i
]
∗
i
+
s
[
i
]
f[k][j-1] + s[k] = a[i] * k + f[i][j] - a[i] * i + s[i]
f[k][j−1]+s[k]=a[i]∗k+f[i][j]−a[i]∗i+s[i]
among
y
=
f
[
k
]
[
j
−
1
]
+
s
[
k
]
y=f[k][j-1] + s[k]
y=f[k][j−1]+s[k]，
k
=
a
[
i
]
k=a[i]
k=a[i]，
b
=
f
[
i
]
[
j
]
−
a
[
i
]
∗
i
+
s
[
i
]
b=f[i][j] - a[i] * i + s[i]
b=f[i][j] − a[i] * i+s[i], and then solve it
code:
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, M = 100010, P = 110;
int n, m, p;
LL d[N], t[N], a[N], s[N];
LL f[P][M];
int q[M];
LL get_y(int k, int j){
return f[j - 1][k] + s[k];
}
int main(){
scanf("%d%d%d", &n, &m, &p);
for (int i = 2; i <= n; i ++ ){
scanf("%lld", &d[i]);
d[i] += d[i - 1];
}
for (int i = 1; i <= m; i ++ ){
int h;
scanf("%d%lld", &h, &t[i]);
a[i] = t[i] - d[h];
}
sort(a + 1, a + m + 1);
for (int i = 1; i <= m; i ++ ) s[i] = s[i - 1] + a[i];
memset(f, 0x3f, sizeof f);
for (int i = 0; i <= p; i ++ ) f[i][0] = 0;
for (int j = 1; j <= p; j ++ ){
int hh = 0, tt = 0;
q[0] = 0;
for (int i = 1; i <= m; i ++ ){
while (hh < tt && (get_y(q[hh + 1], j) - get_y(q[hh], j)) <= a[i] * (q[hh + 1] - q[hh])) hh ++ ;
int k = q[hh];
f[j][i] = f[j - 1][k] - a[i] * k + s[k] + a[i] * i - s[i];
while (hh < tt && (get_y(q[tt], j) - get_y(q[tt - 1], j)) * (i - q[tt]) >=
(get_y(i, j) - get_y(q[tt], j)) * (q[tt] - q[tt - 1])) tt -- ;
q[ ++ tt] = i;
}
}
printf("%lld\n", f[p][m]);
return 0;
}