斜率優化 筆記

梗概

目前隻會斜率優化的naive的版本，動态維護凸包的版本目前不會，以後會的時候再更新

我們在做dp問題時經常性的會發現時間複雜度完全不夠，那麼我們需要用到優化了

dp的優化有很多，這裡不再贅述，單說斜率優化。

總條件

f[i]=max(f[k]+g[i]*g[k]+b)(有決策點k的狀态，有i和k的狀态，有常數b)

然後将常數項和目前要求的f[i]算作B

B=f[i]+b B = f [ i ] + b

将隻與f[k]有關的算作y

y=f[k]+... y = f [ k ] + . . .

将與g[k]和g[i]有關的 g[k]算作x g[i]算作k

B=y+k∗x==>y=B−k∗x B = y + k ∗ x ==> y = B − k ∗ x

然後就是類似于數學中的線性規劃問題，用一條斜率是定值的直線求和之前狀态構成的凸包的交點，交點就是目前的決策點。

情況一：若決策的橫坐标 x[j] x [ j ] 和斜率 k k 單調，我們隻需維護一個單調隊列

每次類似Graham−ScanGraham−Scan算法一樣加點、删點

詢問時根據斜率單調移動詢問指針

時間複雜度為 O(n) O ( n )

情況二：若決策的橫坐标 x[j] x [ j ] 和斜率 k k 不單調，我們則需要一個進階資料結構來動态維護凸包，顯然平衡樹能夠勝任

加點時我們需要二分橫坐标位置，并左右删點以維護凸殼凸性

在詢問時則需二分凸殼的斜率以得到直線與凸殼的切點

時間複雜度為O(nlogn)O(nlogn)

引用劉明華dalao的課件内容。

[HNOI2008]玩具裝箱toy

一道較為好想的dp題

暴力異常好想：

f[j]=min(f[k]+(j−k−1+sum[j]−sum[k]−L)2) f [ j ] = m i n ( f [ k ] + ( j − k − 1 + s u m [ j ] − s u m [ k ] − L ) 2 )

下面稍微整一下

g[i]=sum[i]+i;L=L+1; g [ i ] = s u m [ i ] + i ; L = L + 1 ; 友善讨論

(g[j]−g[k]−L)2=g[j]∗g[j]−2∗g[j]∗L+L∗L+g[k]∗g[k]−2∗g[k]∗g[j]+2∗L∗g[k]; ( g [ j ] − g [ k ] − L ) 2 = g [ j ] ∗ g [ j ] − 2 ∗ g [ j ] ∗ L + L ∗ L + g [ k ] ∗ g [ k ] − 2 ∗ g [ k ] ∗ g [ j ] + 2 ∗ L ∗ g [ k ] ;

移一下項

f[j]+2∗g[j]∗L−L∗L−g[j]∗g[j]=f[k]+2∗L∗g[k]+g[k]∗g[k]−2∗g[k]∗g[j] f [ j ] + 2 ∗ g [ j ] ∗ L − L ∗ L − g [ j ] ∗ g [ j ] = f [ k ] + 2 ∗ L ∗ g [ k ] + g [ k ] ∗ g [ k ] − 2 ∗ g [ k ] ∗ g [ j ]

B=f[j]+2∗g[j]∗L−L∗L−g[j]∗g[j]; B = f [ j ] + 2 ∗ g [ j ] ∗ L − L ∗ L − g [ j ] ∗ g [ j ] ;

y=f[k]+g[k]∗g[k]+2∗L∗g[k]; y = f [ k ] + g [ k ] ∗ g [ k ] + 2 ∗ L ∗ g [ k ] ;

k=−2∗g[j]; k = − 2 ∗ g [ j ] ;

x=g[k]; x = g [ k ] ;

B=y+kx; B = y + k x ;

y=−kx+B; y = − k x + B ;

這樣就可以dp優化了，用單調隊列維護

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=+;
ll f[maxn],g[maxn],sum[maxn],a[maxn];
int n;
ll L;
struct node
{
    ll x,y; int id;
}q[maxn];
double getk(int x,int y)
{
    return (q[y].y-q[x].y)*1./(q[y].x-q[x].x);
}
int main()
{
    freopen("bzoj_1010.in","r",stdin);
    freopen("bzoj_1010.out","w",stdout);
    scanf("%d %lld",&n,&L); L++;
    for(int i=; i<=n; i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-]+a[i]; g[i]=sum[i]+i;
    }
    int head=,tail=;
    for(int i=; i<=n; i++)
    {
        while(head<tail && getk(head,head+)<=*g[i]) head++;
        f[i]=-*g[i]*q[head].x+q[head].y-*g[i]*L+L*L+g[i]*g[i];
        ll y=f[i]+g[i]*g[i]+*L*g[i],x=g[i];
        while(tail>head && ((y-q[tail-1].y)*1./(x-q[tail-1].x))<getk(tail,tail-)) tail--;
        tail++; q[tail].y=y; q[tail].x=x; q[tail].id=i;
    //  cout<<f[i]<<endl;
    }
    cout<<f[n]<<endl;
    return ;
}