博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
DP的优化（斜率优化）
阅读量：3950 次
发布时间：2019-05-24

本文共 17362 字，大约阅读时间需要 57 分钟。

文章目录

斜率优化

易得朴素思路，但时间复杂度超过1e8。
d p [ i ] = m i n ( d p [ j ] + ( s u m [ i ] + i − s u m [ j ] − j − L − 1 ) 2 ) , i > j dp[i]=min(dp[j]+(sum[i]+i−sum[j]−j−L−1)^2),i>j dp[i]=min(dp[j]+(sum[i]+i−sum[j]−j−L−1)2),i>j
设 A i = s u m [ i ] + i , B j = s u m [ j ] + L + j + 1 A_i=sum[i]+i, B_j=sum[j]+L+j+1 Ai​=sum[i]+i,Bj​=sum[j]+L+j+1化简得
d p [ i ] = d p [ j ] + A i 2 − 2 A i B j + B j 2 2 A i B j + d p [ i ] − A i 2 = d p [ j ] + B j 2 k ∗ x      +            b           =         y dp[i]=dp[j]+A_i^2-2A_iB_j+B_j^2\\ 2A_iB_j+dp[i]-A_i^2=dp[j]+B_j^2\\ k*x\ \ \ \ + \ \ \ \ \ \ \ \ \ \ b\ \ \ \ \ \ \ \ \ =\ \ \ \ \ \ \ y dp[i]=dp[j]+Ai2​−2Ai​Bj​+Bj2​2Ai​Bj​+dp[i]−Ai2​=dp[j]+Bj2​k∗x    +          b         =       y
可把 2 A i 2A_i 2Ai​看成k，把 d p [ i ] − A i 2 dp[i]-A_i^2 dp[i]−Ai2​看成b，把 d p [ j ] + B j 2 dp[j]+B_j^2 dp[j]+Bj2​看成y。现在要 m i n   d p [ i ] min\ dp[i] min dp[i]即可求前面一堆点中找一个点让斜率固定的直线的截距最小化。
让截距最小化的方式是求凸包，并维护凸包最左边的线段斜率大于当前的 2 A i 2A_i 2Ai​。因为 2 A i 2A_i 2Ai​是随着 i i i单调递增的，斜率一直在增加。凸包最左边的线段斜率小于当前的 2 A i 2A_i 2Ai​时，最左边那个点现在没用，后面更加没用。
单调队列斜率优化的步骤:

  1. 弹队头,就是最左边的点，直到斜率大于 2 A i 2A_i 2Ai​.
  2. 放直线,算答案,得到当前状态的答案,得到新的待加入的点.
  3. 弹队尾,把插入新点之后不合法的点弹掉（维护凸包），最后加入新点就好了.

用我的计算几何模的板码

#include
   
    using namespace std;using ll = long long;using pii = pair
    
     ;using pll = pair
     
      ;const int maxn = 5e4 + 5;struct Coor{
       ll x, y;    Coor operator- (const Coor &ot) const &{
           return Coor{
   x-ot.x, y-ot.y};    }    ll operator^ (const Coor &ot) const &{
           return x*ot.y - y*ot.x;    }    double getk(){
           return double(y) / x;    }}sta[maxn];ll dp[maxn], sum[maxn], n, L;ll A(int i){
       return i + sum[i];}ll B(int j){
       return j + L + 1 + sum[j];}ll gety(int j){
       return dp[j] + B(j) * B(j);}int main(){
       cin >> n >> L;    for(int tv, i = 1; i <= n; ++i){
           cin >> sum[i];        sum[i] += sum[i - 1];    }    dp[0] = 0;    sta[0] = Coor{
   B(0), dp[0] + B(0)*B(0)};    int tail = 0, head=0;    for(int i=1;i<=n;++i){
           while(head
      
        head && ((sta[tail] - sta[tail-1]) ^ (now - sta[tail])) < 0)tail--;        sta[++tail] = now;    }    cout << dp[n] << endl;}

转载自

这题比上一题多加了个限制，必须最后要分成了 m m m段。所以要加多一个维度，第 i i i段的要在第 i − 1 i-1 i−1段上操作。所以上面斜率优化DP三步走的操作上有点不同，更新 f [ i ] [ j ] f[i][j] f[i][j]时，应该把 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]的对应坐标插入凸包中，已方便更新 f [ i ] [ j + 1 ] f[i][j+1] f[i][j+1]。

#include
   
    using namespace std;using ll = long long;using ld = long double;using pii = pair
    
     ;using pll = pair
     
      ;const int maxn = 3e3 + 5;const ll mod = 1e9 + 7;struct Coor{
       ll x, y;    ll operator^ (const Coor & ot) const & {
           return x*ot.y - y*ot.x;    }    Coor operator- (const Coor & ot) const & {
           return Coor{
   x-ot.x, y-ot.y};    }    ld k(){
           return ld(y) / x;    }}sta[maxn];ll n, m, a[maxn], pre[maxn], f[maxn][maxn], sum = 0, head, tail;ll getY(int k, int j){
       return f[k][j] + pre[j] * pre[j];}ll getX(int j){
       return pre[j];}int main(){
       ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    cin >> n >> m;    for(int i=1;i<=n;++i){
           cin >> a[i];        pre[i] = sum += a[i];    }    for(int j=1;j<=n;++j){
           f[1][j] = pre[j] * pre[j];    }    for(int i=2;i<=m;++i){
           head = tail = 0;        for(int j=1;j<=n;++j){
               while(head < tail && (sta[head+1] - sta[head]).k() <= 2*pre[j])head++;            f[i][j] = sta[head].y - 2*pre[j]*sta[head].x + pre[j]*pre[j];            Coor now = Coor{
   pre[j], getY(i-1, j)};            while(head < tail && ((sta[tail] - sta[tail-1]) ^ (now - sta[tail])) <= 0)tail--;            sta[++tail] = now;        }    }    cout << m*f[m][n] - sum * sum << endl;}

单调队列优化

适用于

f ( x ) = min ⁡ k = b [ x ] x − 1 { g ( k ) + w [ x ] } ， 其 中 b [ x ] 随 x 不 降 f(x)=\min_{k=b[x]}^{x-1}\{g(k)+w[x]\}，其中b[x]随x不降 f(x)=k=b[x]minx−1​{
g(k)+w[x]}，其中b[x]随x不降
对于每一个状态f(x)，计算过程如下

  1. 队首元素持续出队，知道队首元素在区间[b[x],x−1]中。
  2. 此时队首元素k即为f(x)的最优决策。
  3. 计算g(x)，将其插入单调队列的尾部，同时维护队列的单调性（将队尾与x不满足单调性的决策全部出队）

参考自、

在这里插入图片描述

#include
   
    using namespace std;using ll = long long;using pii = pair
    
     ;using pll = pair
     
      ;const int maxn = 2e5 + 5, maxm = 3e2 + 5;ll n, m, d;int a[maxm], b[maxm], t[maxm];ll f[2][maxn];int main(){
       ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    cin >> n >> m >> d;    for(int i=0;i
      
       > a[i] >> b[i] >> t[i];    }    for(int j=1;j<=n;++j){
           f[0][j] = b[0] - abs(a[0] - j);    }    for(int i=1;i
dq; for(int j=1;j<=min(1+d*dt, n);++j){
while(!dq.empty() && f[!(i&1)][dq.back()] <= f[!(i&1)][j]) dq.pop_back(); dq.push_back(j); } for(int j=1;j<=n;++j){
while(!dq.empty() && dq.front() < j - d * dt)dq.pop_front(); f[i&1][j] = f[!(i&1)][dq.front()] + b[i] - abs(a[i] - j); if(j + d * dt + 1 > n)continue; while(!dq.empty() && f[!(i&1)][dq.back()] <= f[!(i&1)][j + d * dt + 1]) dq.pop_back(); dq.push_back(j + d * dt + 1); } } ll ans = -2e18; for(int j=1;j<=n;++j){
ans = max(ans, f[(m-1)&1][j]); } cout << ans << endl;}

思路：
假设向下倾斜，第 k k k次倾斜时
f 1 [ i ] [ j ] = max ⁡ { f 0 [ i ] [ v ] + j − v } , j + t [ k ] − s [ k ] ≤ v ≤ j f1[i][j]=\max\{f0[i][v]+j-v\},\quad j+t[k]-s[k]\le v \le j f1[i][j]=max{
f0[i][v]+j−v},j+t[k]−s[k]≤v≤j
设 d t = t [ k ] − s [ k ] dt=t[k]-s[k] dt=t[k]−s[k]，则可得下式，可以看出 j + d t j+dt j+dt随 j j j单调递增， f 0 [ i ] [ v ] − v f0[i][v]-v f0[i][v]−v看做整体，可以用单调递减队列优化。
f 1 [ i ] [ j ] = max ⁡ { f 0 [ i ] [ v ] − v } + j , j + d t ≤ v ≤ j f1[i][j]=\max\{f0[i][v]-v\}+j,\quad j+dt\le v \le j f1[i][j]=max{
f0[i][v]−v}+j,j+dt≤v≤j
要注意的是，当遇到家具时要清空队列。当队列为空时，标记该位置不可抵达。

#include
   
    #define ne(__x) cout << #__x << ": " << __x << endl;#define ns(__x) cout << #__x << ": " << __x << " ";#define ps(__x) cout << __x << " ";#define pe(__x) cout << __x << endl;using namespace std;using ll = long long;using pii = pair
    
     ;using pll = pair
     
      ;const int maxn = 2e5 + 5, maxm = 3e2 + 5;int n, m, x, y, k;int s[205], t[205], d[205];int f[2][205][205];char a[205][205];int main(){
       ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    cin >> n >> m >> x >> y >> k;    for(int i=1;i<=n;++i){
           for(int j=1;j<=m;++j){
               cin >> a[i][j];        }    }    for(int i=1;i<=k;++i){
           cin >> s[i] >> t[i] >> d[i];    }    memset(f, -1, sizeof(f));    f[0][x][y] = 0;    auto f0 = f[0], f1 = f[1];    for(int q=1;q<=k;++q){
           int dt = t[q] - s[q] + 1;        if(d[q]==1){
               for(int j=1;j<=m;++j){
                   deque
      
        Q;                for(int i=n;i>=1;--i){
                       if(a[i][j] == 'x'){
   f1[i][j] = -1; Q.clear(); continue;}                    while(!Q.empty() && f0[Q.back()][j] + Q.back() <= f0[i][j] + i)Q.pop_back();                    if(~f0[i][j]) Q.push_back(i);                    while(!Q.empty() && Q.front() > i + dt) Q.pop_front();                    if(Q.empty()) f1[i][j] =  -1;                    else f1[i][j] = f0[Q.front()][j] + Q.front() - i;                }            }        }else if(d[q]==2){
               for(int j=1;j<=m;++j){
                   deque
       
         Q;                for(int i=1;i<=n;++i){
                       if(a[i][j] == 'x'){
   f1[i][j] = -1; Q.clear(); continue;}                    while(!Q.empty() && f0[Q.back()][j] - Q.back() <= f0[i][j] - i)Q.pop_back();                    if(~f0[i][j]) Q.push_back(i);                    while(!Q.empty() && Q.front() < i - dt) Q.pop_front();                    if(Q.empty()) f1[i][j] =  -1;                    else f1[i][j] = f0[Q.front()][j] + i - Q.front();                }            }        }        else if(d[q]==3){
               for(int i=1;i<=n;++i){
                   deque
        
          Q; for(int j=m;j>=1;--j){ if(a[i][j] == 'x'){ f1[i][j] = -1; Q.clear(); continue;} while(!Q.empty() && f0[i][Q.back()] + Q.back() <= f0[i][j] + j)Q.pop_back(); if(~f0[i][j]) Q.push_back(j); while(!Q.empty() && Q.front() > j + dt) Q.pop_front(); if(Q.empty()) f1[i][j] = -1; else f1[i][j] = f0[i][Q.front()] + Q.front() - j; } } }else if(d[q]==4){ for(int i=1;i<=n;++i){ deque
         
           Q; for(int j=1;j<=m;++j){ if(a[i][j] == 'x'){ f1[i][j] = -1; Q.clear(); continue;} while(!Q.empty() && f0[i][Q.back()] - Q.back() <= f0[i][j] - j)Q.pop_back(); if(~f0[i][j]) Q.push_back(j); while(!Q.empty() && Q.front() < j - dt) Q.pop_front(); if(Q.empty()) f1[i][j] = -1; else f1[i][j] = f0[i][Q.front()] + j - Q.front(); } } } swap(f0, f1); } int ans = 0; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ ans = max(ans, f0[i][j]); // ps(f0[i][j]); } // cout << endl; } cout << ans << endl;}

定义 f [ i ] [ j ] f[i][j] f[i][j]为第 i i i天拥有 j j j股股票的变现收益
f [ i ] [ j ] = m a x { f [ i − 1 ] [ j ] 今 天 不 操 作 − A P [ i ] ∗ j ,   j < A S [ i ] 第 一 次 买 入 f [ i − w − 1 ] [ x ] + ( x − j ) A P [ i ] ,   j − A S [ i ] ≤ x ≤ j 今 天 买 入 f [ i − w − 1 ] [ x ] + ( x − j ) B P [ i ] ,   j ≤ x ≤ j + B S [ i ] 今 天 卖 出 f[i][j]=max\begin{cases} f[i-1][j] &今天不操作\\ -AP[i]*j,\ j<AS[i] &第一次买入\\ f[i-w-1][x]+(x-j)AP[i],\ j-AS[i]\le x \le j &今天买入\\ f[i-w-1][x]+(x-j)BP[i],\ j\le x \le j+BS[i] &今天卖出 \end{cases} f[i][j]=max⎩⎪⎪⎪⎨⎪⎪⎪⎧​f[i−1][j]−AP[i]∗j, j<AS[i]f[i−w−1][x]+(x−j)AP[i], j−AS[i]≤x≤jf[i−w−1][x]+(x−j)BP[i], j≤x≤j+BS[i]​今天不操作第一次买入今天买入今天卖出​
买入和卖出可以变换成 { g ( x ) + w [ j ] } \{g(x)+w[j]\} {
g(x)+w[j]}的形式，而x的窗口随着 j j j增加。所以可以单调队列优化。
f [ i ] [ j ] = m a x { f [ i − 1 ] [ j ] 今 天 不 操 作 − A P [ i ] ∗ j ,   j < A S [ i ] 第 一 次 买 入 ( f [ i − w − 1 ] [ x ] + x ⋅ A P [ i ] ) − j ⋅ A P [ i ] ,   j − A S [ i ] ≤ x ≤ j 今 天 买 入 ( f [ i − w − 1 ] [ x ] + x ⋅ B P [ i ] ) − j ⋅ B P [ i ] ,   j ≤ x ≤ j + B S [ i ] 今 天 卖 出 f[i][j]=max\begin{cases} f[i-1][j] &今天不操作\\ -AP[i]*j,\ j<AS[i] &第一次买入\\ (f[i-w-1][x]+x\cdot AP[i])-j\cdot AP[i],\ j-AS[i]\le x \le j &今天买入\\ (f[i-w-1][x]+x\cdot BP[i])-j\cdot BP[i],\ j\le x \le j+BS[i] &今天卖出 \end{cases} f[i][j]=max⎩⎪⎪⎪⎨⎪⎪⎪⎧​f[i−1][j]−AP[i]∗j, j<AS[i](f[i−w−1][x]+x⋅AP[i])−j⋅AP[i], j−AS[i]≤x≤j(f[i−w−1][x]+x⋅BP[i])−j⋅BP[i], j≤x≤j+BS[i]​今天不操作第一次买入今天买入今天卖出​

#include
   
    using namespace std;using ll = long long;using pii = pair
    
     ;using pll = pair
     
      ;const int maxn = 2e5 + 5, maxm = 3e2 + 5;ll T, MaxP, w;ll ap[2005], bp[2005], as[2005], bs[2005];ll f[2005][2005];int main(){
       ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    memset(f, 0x80, sizeof(f));    cin >> T >> MaxP >> w;    for(int i=1;i<=T;++i){
           cin >> ap[i] >> bp[i] >> as[i] >> bs[i];        bs[i] = min(bs[i], MaxP);        as[i] = min(as[i], MaxP);    }    for(int j=0;j<=min(MaxP, as[1]);++j){
           f[1][j] = -ap[1] * j;    }    for(int i=2;i<=T;++i){
   //        for(int j=0;j<=MaxP;++j)//            cout << f[i-1][j] << ' ';//        cout << endl;        deque
      
        AQ, BQ;        if(i-w-1 > 1){
               for(int j=0;j

平行四边形优化

区间类(2D/1D)动态规划应用

解决形如

f i , j = min ⁡ i ≤ k < j f i , k + f k + 1 , j + ω ( i , j ) f_{i, j} = \min_{i\le k < j} f_{i, k} + f_{k+1, j} + \omega(i,j) fi,j​=i≤k<jmin​fi,k​+fk+1,j​+ω(i,j)
必须满足以下条件：

  • 求的是最小值
  • ω ( i , j ) \omega(i,j) ω(i,j)符合区间包含单调性，即 l ≤ l ′ ≤ r ′ ≤ r ,   ω ( l ′ , r ′ ) ≤ ω ( l , r ) l\le l'\le r'\le r,\ \omega(l',r')\le\omega(l,r) l≤l′≤r′≤r, ω(l′,r′)≤ω(l,r)
  • ω ( i , j ) \omega(i,j) ω(i,j)符合四边形不等式（交叉小于包含），即 l 1 ≤ l 2 ≤ r 1 ≤ r 2 ,   ω ( l 1 , r 1 ) + ω ( l 2 , r 2 ) ≤ ω ( l 1 , r 2 ) + ω ( l 2 , r 1 ) l_1\le l_2\le r_1\le r_2,\ \omega(l_1,r_1) + \omega(l_2,r_2) \le \omega(l_1,r_2) + \omega(l_2,r_1) l1​≤l2​≤r1​≤r2​, ω(l1​,r1​)+ω(l2​,r2​)≤ω(l1​,r2​)+ω(l2​,r1​)

快速判断是否满足"交叉小于包含"

由于 l 1 ≤ l 2 ≤ r 1 ≤ r 2 ,   ω ( l 1 , r 1 ) + ω ( l 2 , r 2 ) ≤ ω ( l 1 , r 2 ) + ω ( l 2 , r 1 ) l_1\le l_2\le r_1\le r_2,\ \omega(l_1,r_1) + \omega(l_2,r_2) \le \omega(l_1,r_2) + \omega(l_2,r_1) l1​≤l2​≤r1​≤r2​, ω(l1​,r1​)+ω(l2​,r2​)≤ω(l1​,r2​)+ω(l2​,r1​)可以调换一下位置得到

ω ( l 1 , r 1 ) − ω ( l 2 , r 1 ) ≤ ω ( l 1 , r 2 ) − ω ( l 2 , r 2 ) \omega(l_1,r_1) - \omega(l_2,r_1) \le \omega(l_1,r_2) - \omega(l_2,r_2) ω(l1​,r1​)−ω(l2​,r1​)≤ω(l1​,r2​)−ω(l2​,r2​)
设 g ( r ) = ω ( l 1 , r ) − ω ( l 2 , r ) g(r)=\omega(l_1,r) - \omega(l_2,r) g(r)=ω(l1​,r)−ω(l2​,r)，则有 r 1 < r 2 ,   g ( r 1 ) ≤ g ( r 2 ) r_1<r_2,\ g(r_1)\le g(r_2) r1​<r2​, g(r1​)≤g(r2​).
即当 g ( j ) = ω ( i , j ) − ω ( i + 1 , j ) g(j)=\omega(i,j) - \omega(i+1,j) g(j)=ω(i,j)−ω(i+1,j)满足随 j j j单调不降，则符合四边形不等式。

引理1：若满足关于区间包含的单调性的函数 ω ( i , j ) \omega(i,j) ω(i,j)满足区间包含单调性和四边形不等式，则状态 f i , j f_{i,j} fi,j​也满足四边形不等式。

定理1

若 f f f符合四边形不等式，记 m l , r = min ⁡ { k : f l , r = g k , l , r } m_{l, r}=\min \left\{k: f_{l, r}=g_{k, l, r}\right\} ml,r​=min{

k:fl,r​=gk,l,r​}表示最优决策点，则有下面两种做法。区间DP用的是第一条。
m l , r − 1 ≤ m l , r ≤ m l + 1 , r m l − 1 , r ≤ m l , r ≤ m l , r + 1 m_{l, r-1} \leq m_{l, r} \leq m_{l+1, r}\\ m_{l-1, r} \leq m_{l, r} \leq m_{l, r+1} ml,r−1​≤ml,r​≤ml+1,r​ml−1,r​≤ml,r​≤ml,r+1​
时间复杂度为 O ( n 2 ) O(n^2) O(n2)，关键代码：

for (int len = 2; len <= n; ++len)  // 枚举区间长度  for (int l = 1, r = len; r <= n; ++l, ++r) {
       // 枚举长度为len的所有区间    f[l][r] = INF;    for (int k = m[l][r - 1]; k <= m[l + 1][r]; ++k)      if (f[l][r] > f[l][k] + f[k + 1][r] + w(l, r)) {
           f[l][r] = f[l][k] + f[k + 1][r] + w(l, r);  // 更新状态值        m[l][r] = k;  // 更新（最小）最优决策点      }  }

对于dp转移合法的证明，其实很多时候不用证明，直接打表就行了，比如先跑一个 O ( n 3 ) O(n^3) O(n3)的代码，跑的时候判断是否满足四边形不等式，决策是否单增等等，如果不满足就输出false之类的，或者打一个决策表出来观察，这样其实会省下一部分时间。

题意：把n个节点分成m块，使得最后价值最小。
思路：
这道题推推公式可以用斜率优化做，但是推公式太慢了。很容易得到dp式子， f f f表示炸了 i i i次，到 j j j点的最小价值。 w ( i , j ) w(i,j) w(i,j)是 i i i到 j j j为一块的代价，可以 O ( n 2 ) O(n^2) O(n2)获得。打表验证 w ( i , j ) w(i,j) w(i,j)四边形不等式，直接优化。
f [ i ] [ j ] = min ⁡ i ≤ k < j f [ i − 1 ] [ k ] + w [ k + 1 ] [ j ] f[i][j]=\min_{i\le k<j} f[i-1][k] + w[k+1][j] f[i][j]=i≤k<jmin​f[i−1][k]+w[k+1][j]

回顾一下四边形优化。首先，他的使用条件是dp数组是由一个满足四边形不等式的w数组相加得来的，即dp数组也满足四边形不等式。这样的话，对于当前状态i、j，dp[i][j]取最有的决策，就在s[i-1][j]到s[i,j-1]之间。如此一来，决策的枚举数量大大减少，达到了优化的效果。

（不是很理解）

#include
   
    #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);using namespace std;const int maxn = 1e3 + 5;int a[maxn], p[maxn][maxn], pre[maxn], f[maxn][maxn], mt[maxn][maxn];int g(int i, int j){
       return p[i-1][j] - p[i][j];}int main(){
       IOS;    int n, m;    while(cin >> n >> m && n && m){
           for(int i = 1; i <= n; ++i){
               // a[i] = rand() % 10 + 1; cout << a[i] << endl;            cin >> a[i];            pre[i] = pre[i - 1] + a[i];        }        for(int i = 1; i <= n; ++i){
               for(int j = i + 1; j <= n; ++j){
                   p[i][j] = p[i][j-1] + (pre[j - 1] - pre[i - 1]) * a[j];            }        }        memset(f, 0x7f, sizeof(f));        for(int i = 0; i <= n; ++i){
               f[0][i] = p[1][i];            mt[0][i] = 0;        }        for(int i = 1; i <= m; ++i){
               mt[i][n + 1] = n - 1;            for(int j = n; j >= i; --j){
                   for(int k = mt[i-1][j]; k <= mt[i][j+1]; ++k){
                       if(f[i - 1][k] + p[k + 1][j] < f[i][j]){
                           f[i][j] = f[i - 1][k] + p[k + 1][j];                        mt[i][j] = k;                    }                }            }        }        cout << f[m][n] << endl;    }}

题意：建立 p p p个邮局，选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。
思路： f [ i ] [ j ] f[i][j] f[i][j]表示 i i i个邮局，前 j j j个点的总代价。 w [ k ] [ j ] w[k][j] w[k][j]表示此区间内做一个邮局的最小代价，其实这个邮局必然在中位数那个点上。同样，打表验证四边形不等式（看注释部分）。
f [ i ] [ j ] = min ⁡ i ≤ k < j f [ i − 1 ] [ k ] + w [ k + 1 ] [ j ] f[i][j]=\min_{i\le k<j} f[i-1][k] + w[k+1][j] f[i][j]=i≤k<jmin​f[i−1][k]+w[k+1][j]

#include
   
    // #define endl '\n'#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);using namespace std;const int N = 3e3 +5;const double eps = 1e-10;using LL = long long;LL pos[N], sp[N], f[N][N], mt[N][N];LL w(int k, int j){
       int mid = k + j >> 1;    return (2 * mid + 1 - j - k) * pos[mid] + (sp[j] + sp[k - 1] - 2 * sp[mid]);}//LL g(int i, int j){
   //    return w(i, j) - w(i + 1, j);//}int main(){
       IOS;    int n, p;    cin >> n >> p;    for(int i = 1; i <= n; ++i){
           cin >> pos[i];    }    sort(pos + 1, pos + n + 1);    for(int i = 1; i <= n; ++i){
           sp[i] = sp[i - 1] + pos[i];    }//    for(int i = 1; i < n; ++i){
   //        for(int j = i; j <= n; ++j){
   //            cout << g(i, j) << " ";//        }//        cout << endl;//    }    memset(f, 0x7f, sizeof(f));    for(int j = 1; j <= n; ++j){
           mt[0][j] = 0;    }    f[0][0] = 0;    for(int i = 1; i <= p; ++i){
           mt[i][n + 1] = n - 1;        for(int j = n; j; --j){
               for(int k = mt[i - 1][j]; k <= mt[i][j + 1]; ++k){
                   LL now = f[i - 1][k] + w(k + 1, j);                if(f[i][j] > now){
                       f[i][j] = now;                    mt[i][j] = k;                }            }        }    }    cout << f[p][n] << endl;}

1D/1D动态规划应用

解决以下形式的问题

f r = min ⁡ l = 1 r − 1 { f l + w ( l , r ) } ( 1 ≤ r ≤ n ) f_{r}=\min _{l=1}^{r-1}\left\{f_{l}+w(l, r)\right\} \quad(1 \leq r \leq n) fr​=l=1minr−1​{
fl​+w(l,r)}(1≤r≤n)

定理2

若 w ( l , r ) w(l, r) w(l,r)符合四边形不等式，则 ∀ 1 ≤ a ≤ b ≤ c ≤ d ≤ N , w a , c + w b , d ≤ w a , d + w b , c \forall 1 \leq a \leq b \leq c \leq d \leq N, w_{a, c}+w_{b, d} \leq w_{a, d}+w_{b, c} ∀1≤a≤b≤c≤d≤N,wa,c​+wb,d​≤wa,d​+wb,c​。当 w a , c ≥ w b , c w_{a, c} \geq w_{b, c} wa,c​≥wb,c​，由上式可得 w a , d ≥ w b , d w_{a, d} \geq w_{b, d} wa,d​≥wb,d​，即

∀ i ≤ j : 最 优 决 策 点 k i ≤ k j \forall i \leq j: 最优决策点k _i \leq k_j ∀i≤j:最优决策点ki​≤kj​

你可能感兴趣的文章
linux学习之tr操作符用法
查看>>
shell的dirname $0和readlink用法
查看>>
设计模式——设计模式三大分类以及六大原则
查看>>
Android开发——ListView局部刷新的实现
查看>>
Android开发——ListView的复用机制源码解析
查看>>
Android开发——架构组件LiveData源码解析
查看>>
IDEA常用快捷键整理
查看>>
【Vue】两个元素同一行显示
查看>>
XXL-Job使用
查看>>
如何在SwaggerAPI中添加统一授权认证
查看>>
多线程
查看>>
【Linux】Centos7 常用命令
查看>>
【Redis】Centos7下安装Redis
查看>>
【Redis】Centos7下搭建Redis集群
查看>>
【Redis】Centos7下搭建Redis集群——哨兵模式
查看>>
【Linux】本地ping不同VM虚拟机
查看>>
【SpringCloud】Hystrix
查看>>
快速阅读——《认知篇》
查看>>
【Asp.net】基本概念
查看>>
【Asp.net】Web服务器控件
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-09-18 21:35:16   当前IP: 3.133.115.42   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我