斜率优化DP
类似于:F [ i ] = min[ L(i) <= j <= R(i)] {F[ j ] + val( i, j)},其中,多项式val(i , j )的每一项仅与 i 和 j 中的一个有关。这种情况的时候,我们一般采用 单调队列优化。如果 多项式 val(i , j )包含 i, j 的乘积项,即存在一个同时与 i 和 j 有关的部分时,应该采用 斜率优化。
300. 任务安排1 - AcWing题库
状态表示: f[ i ] [ j ] 表示前 i 个任务,分成 j 批来完成的最小花费。 属性 :最小值。
状态计算:从题干中得知,任务分批完成,且花费的计算是按照 整批任务全部完成的时间 来计算,容易想到,处理时分批计算。
? F [ i ] [ j ] = min (0 <= k < i) { F[k] [ j - 1 ] + (S * j + sumT[ i ]) * ( sumC[ i ] - sumC[ k ]) }
这样的解法时间复杂度为 O(N ^3)。
事实上,我们不容易直接得知在此之前及其启动过几次。但我们指导,机器因执行这批任务而花费的启动时间S,会累加到在此之后所有任务的完成时刻上。所以,如果把 分成的批次 j 这一维度优化掉,设 F [ i ] 为前 i 个任务分成若干批执行的最小费用,状态转移方程也容易得出:
? F [ i ] = min ( 0 <= j < i ) { F[ j ] + sumT[ i ] * (sumC[ i ] - sumC[ j ]) + S * (sumC [ N ] - sumC [ j ] )}
我个人认为,这一维度的优化,是因为 在进行状态计算的过程中,都是以最后一个状态 选 or 不选 来进行转移的。也就是说,是否知道之前已经进行过的轮数是不必要的,属于冗余运算。所以可以优化掉这一维度的时间复杂度。
这样计算,我们没有直接求出每批任务的完成时刻,而是在一批任务”开始“对后继任务产生的影响是,就先把费用累加到答案中。这就是” 费用提前计算 “的思想。
经过优化后,时间复杂度降低为 O(n^2)。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e3+10;
LL f[N],sumt[N],sumc[N];
int n,s;
int main()
{
scanf("%d %d",&n,&s);
for(int i=1;i<=n;i++)
{
int t,c;
scanf("%d %d",&t,&c);
sumt[i] = sumt[i-1] + t;
sumc[i] = sumc[i-1] + c;
}
memset(f,0x3f,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] + sumt[i]*(sumc[i] - sumc[j]) + s*(sumc[n] - sumc[j]));
}
cout<<f[n]<<endl;
return 0;
}
301. 任务安排2 - AcWing题库
寄了,还好之前学过计算几何,要不真听不懂。细节方面还是lyd的蓝书和Y总的视频。(这节蓝书竟然能看懂,雷姆~)
AcWing 301. 任务安排2(算法提高课) - AcWing
大体的思想就是:把状态计算的式子去min,然后进行线性规划,把含 j 的两个式子分别当作 x 和 y,然后对 所有的 j (现在对应到图中的所有点)看哪一个点能取到最小的截距(因为F[ i ]是截距中的唯一变量,且符号为正,截距最小就是F[ i ]最小)。
然后就是单调队列 + 维护下凸包。
具体内容从蓝书P323开始,这里先记录以下算法过程:
- 检查队头的两个决策变量 q[ l ] 和 q[ l + 1] ,若斜率 (F[q[ l + 1]] - F[ q[ l ]]) / (sumC[q[ l + 1]] - sumC[q[ l ]]) <= S + sumT[ i ],则把q[ l ] 出队,继续检查新的队头。
- 直接取队头 j = q[ l ] 为最优决策,执行状态转移,计算出 F [ i ]。
- 把新决策 i 从队尾插入,在插入之前,若三个决策点 j1 = q[r-1], j2 = q[ r ], j3 = i 不满足斜率单调递增,(即不满足下凸性,j2就是无用决策),则直接从队尾把q[ r ]出队,继续检查心的队尾。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
typedef long long LL;
int n,s;
LL c[N], t[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++)
{
while(hh < tt && (f[q[hh+1]] - f[q[hh]]) <= (c[q[hh+1]] - c[q[hh]]) * (s + t[i]) ) hh++;
int j = q[hh];
f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
while(hh < tt && (__int128)(f[q[tt]] - f[q[tt-1]])*(c[i] - c[q[tt - 1]]) >= (__int128)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt--;
q[++tt] = i;
}
printf("%lld\n",f[n]);
return 0;
}
302. 任务安排3 - AcWing题库
执行时间T可能是符数,所以sumT不具有单调性,即我们的直线斜率不具有单调性,但是凸包还是有单调性的。我们就不能O(1)的取队头元素作为最优解,而是应该在整个队列中二分当前直线斜率,即 S + sumT[ i ] ,的位置。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
typedef long long LL;
int n,s;
LL c[N], t[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]] > (c[q[mid+1]] - c[q[mid]]) * (s + t[i])) r = mid; //check函数:如果某点的斜率比当前点大, 则返回true,否则返回false
else l = mid + 1;
}
int j = q[l];
f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
while(hh < tt && (__int128)(f[q[tt]] - f[q[tt-1]])*(c[i] - c[q[tt - 1]]) >= (__int128)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt--;
q[++tt] = i;
}
printf("%lld\n",f[n]);
return 0;
}
- 分析问题:差分、前缀和、分析题目性质,看是否需要排序来消除后效性。
- 确定状态:一般来说是按经验。(??)
- 状态计算:根据确定状态的最后一个,选,还是不选,或是选几个,来分割状态,进行状态转移。并写出状态转移方程。
- DP优化:看状态转移方程是否符合 F [ i ] = min[ L(i) <= j <= R(i)] {F[ j ] + val( i, j)} ,并根据多项式 val( i , j ) 的特性(是只含i / j 还是有i , j 的乘积)来确定采用 单调队列 / 斜率 优化的方式。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10, M = 1e5+10, 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+1+m);
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;
}