Giải thuật Chi tiết

Ví dụ Đầu vào

Chúng ta hãy xem một bài toán: Đóng gói đồ chơi.

Có \(n\) món đồ chơi, món đồ chơi thứ \(i\) có chiều dài \(c_i\). Yêu cầu xếp \(n\) món đồ chơi này theo thứ tự thành một hàng và chia thành một số đoạn. Chi phí của một đoạn \([l,r]\) là \((r-l+\sum_{i=l}^{r} c_i-L)^2\), hãy tìm cách chia đoạn có tổng chi phí nhỏ nhất.

\(1 \le n \le 5 \times 10^4\), \(1 \le c_i,L \le 10^7\).

Phương pháp Quy hoạch Động Tự nhiên

Đầu tiên, ta có thể nghĩ đến một phương pháp Quy hoạch Động tự nhiên.

Gọi \(dp_i\) là tổng chi phí nhỏ nhất khi chia \(i\) món đồ chơi đầu tiên thành các đoạn, kết quả cuối cùng chính là \(dp_n\).

Ta tính trước tổng tiền tố \(s_k = \sum_{i=1}^{k} c_i\), dễ dàng có công thức chuyển trạng thái \(dp_i = \min_{j<i} \{ dp_j + (i-j-1+s_i-s_j)^2 \}\.

Phương pháp này khả thi, nhưng với phạm vi dữ liệu \(5 \times 10^4\) của bài toán, phương pháp bạo lực \(O(n^2)\) này không đủ nhanh để chạy qua.

Tối ưu hóa Hệ số Độ dốc cho Quy hoạch Động

Xem xét đơn giản hóa công thức chuyển trạng thái trên, đặt \(g_i = s_i + i\), \(L' = L + 1\), ta có \(dp_i = \min_{j<i} \{ dp_j + (g_i - g_j - L')^2 \}\)

Chuyển các hạng không phụ thuộc vào \(j\) ra ngoài, ta có \(dp_i - (g_i - L')^2 = \min_{j<i} \{ dp_j + {g_j}^2 + 2s_j(L'-s_i) \}\.

Phương trình tuyến tính dạng \(y = kx+b\), chuyển vế được \(b = y - kx\), biểu diễn tất cả thông tin chỉ phụ thuộc vào \(j\) dưới dạng \(y\), đồng thời các hạng phụ thuộc cả vào \(i\) và \(j\) dưới dạng \(kx\), và lượng cần tối thiểu hóa (chỉ phụ thuộc vào \(i\)) dưới dạng \(b\), ta có \(x_j = g_j\), \(y_j = dp_j + {g_j}^2\), \(k_i = -2(L'-g_i)\), \(b_i = f_i - (s_i - L')^2\).

Vậy công thức chuyển trạng thái có thể viết lại thành \(b_i = \min_{j<i} \{y_j - k_i x_j\}\). Coi \((x_j,y_j)\) là các điểm trên mặt phẳng hai chiều, thì \(k_i\) là hệ số góc, \(b_i\) là đoạn chắn. Vấn đề chuyển thành chọn \(j\) phù hợp để đoạn chắn của đường thẳng là nhỏ nhất.

mượndùng hình ảnh từ OI-wiki:

Không khó thấy rằng, ta có thể dịch chuyển đường thẳng có hệ số góc \(k\) (đường màu đỏ) từ dưới lên trên, cho đến khi có một điểm \((x_p,y_p)\) nằm trên đường thẳng, lúc này \(b_i = y_p - k_i x_p\) và \(b_i\) đạt giá trị nhỏ nhất, sau khi tính xong \(dp_i\) thì thêm điểm \((x_i,y_i)\) vào tập điểm.

Ý tưởng này hay, nhưng làm thế nào để duy trì tập điểm? Lưu ý rằng điểm có thể làm \(b_i\) đạt giá trị nhỏ nhất nhất định nằm trên vỏ lồi dưới, do đó khi tìm kiếm \(p\) ta không cần duy trì toàn bộ tập điểm, chỉ cần duy trì các điểm trên vỏ lồi là đủ. Trong bài toán này, hệ số góc \(k_i\) tăng khi \(i\) tăng, do đó có thể dùng hàng đợi đơn để duy trì.

Quy trình cụ thể khá đơn giản. Mỗi lần chỉ cần dùng một đường thẳng liên quan đến \(i\) để cắt vỏ lồi được duy trì, tìm ra điểm tối ưu để cập nhật \(dp_i\). Sau đó thêm trạng thái \(dp_i\) vào hàng đợi đơn, lúc này cần loại bỏ trước đó tất cả các điểm không còn nằm trên vỏ lồi sau khi thêm điểm mới.

Tham khảo mã thực hiện

Lưu ý rằng khi so sánh phân số nên dùng phương pháp nhân chéo để chuyển thành số nguyên, tránh sai số độ chính xác.

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define i128 __int128
using namespace std;
const int N = 5e4+5;
struct line{LL k,b;};
LL n,L,c[N],s[N],dp[N];
deque<line> q;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
LL tinhY(line ln,LL x){return ln.k*x+ln.b;}
bool KhongHopLe(line l1,line l2,line l3){
    i128 Lx=(i128)(l2.b-l1.b)*(l2.k-l3.k);
    i128 Rx=(i128)(l3.b-l2.b)*(l1.k-l2.k);
    return (Lx>=Rx);
}
int main(){
    n=read(),L=read()+1;
    for(int i=1;i<=n;i++)
        c[i]=read(),s[i]=s[i-1]+c[i]+1;
    q.pb({0,0});
    for(int i=1;i<=n;i++){
        LL x=s[i]-L;
        while(q.size()>1&&tinhY(q[0],x)>=tinhY(q[1],x))q.pop_front();
        LL Bnow=tinhY(q.front(),x);dp[i]=Bnow+x*x;
        line newln={-2*s[i],dp[i]+s[i]*s[i]};
        while(q.size()>1&&KhongHopLe(q[q.size()-2],q.back(),newln))q.pop_back();
        q.pb(newln);
    }cout<<dp[n]<<"\n";
    return 0;
}

Ví dụ Giải thích

P2365 Phân công Công việc

Cho \(n\) công việc được sắp xếp theo một thứ tự nhất định, yêu cầu chia \(n\) công việc này thành một số lô, mỗi lô chứa một số công việc liền kề. Các công việc này bắt đầu được xử lý theo lô từ thời điểm \(0\), thời gian xử lý riêng của mỗi công việc là \(t_i\), và trước mỗi lô công việc có thời gian khởi động máy \(s\), trong khi thời gian hoàn thành một lô công việc là tổng thời gian của các công việc trong đó (các công việc trong cùng một lô sẽ hoàn thành cùng một thời điểm). Chi phí của mỗi công việc là thời điểm hoàn thành của nó nhân với một hệ số chi phí \(f_i\), hãy xây dựng một phương án phân nhóm để tổng chi phí là nhỏ nhất.

\(1\le n \le 5000\), \(0 \le s \le 50\), \(1\le t_i,f_i \le 100\).

Đầu tiên, ta duy trì hai mảng \(st\) và \(sf\) lần lượt là tổng tiền tố của hai mảng \(t\) và \(f\), để thuận tiện cho việc chuyển trạng thái sau này.

Định nghĩa \(dp_i\) là tổng chi phí nhỏ nhất khi chia \(i\) công việc đầu tiên thành các lô, nhưng khi chuyển trạng thái thì ta không biết máy đã khởi động bao nhiêu lần. Tuy nhiên có thể thấy rằng, nếu chuyển từ \(dp_j\) sang \(dp_i\), do các công việc có số thứ tự từ \(j+1 \sim i\) đều hoàn thành trong cùng một lô, do đó chỉ cần bổ sung vào chi phí ảnh hưởng bổ sung của \(s\) cho đoạn này là được.

Vậy ta có công thức chuyển trạng thái \(dp_i = \max\{ dp_j + st_i(sf_i - sf_j) + s(sf_n - sf_j) \}\), độ phức tạp thời gian \(O(n^2)\).

Với phạm vi dữ liệu của bài toán chỉ là \(5000\), làm trực tiếp như vậy đã có thể AC, nhưng chúng ta vẫn hãy xem xét cách tối ưu hóa bằng hệ số độ dốc.

Biến đổi và chuyển hóa công thức, ta có thể thấy hệ số góc \(k_i = s + st_i\), đoạn chắn \(b_i = dp_i - st_i sf_i - s \times sf_n\).

Xem xét \(j_1 < j_2 < j_3\), phân tích điều kiện để \(j_2\) trở thành quyết định tối ưu, thông qua việc vẽ đồ thị và phân tích công thức, ta có thể thấy rằng, khi và chỉ khi \(\dfrac{dp_{j_2} - dp_{j_1}}{sf_{j_2} - sf_{j_1}} < \dfrac{dp_{j_3} - dp_{j_2}}{sf_{j_3} - sf_{j_2}}\), tương đương với việc chúng ta cần duy trì một vỏ lồi dưới có hệ số góc tăng dần. Vì \(0 \le j < i\), khi \(i\) tăng, sẽ có các quyết định mới, nếu chỉ giữ lại phần có hệ số góc giữa các điểm liền kề lớn hơn \(s+st_i\), thì điểm bên trái nhất chính là quyết định tối ưu.

Vậy độ phức tạp thời gian được tối ưu hóa thành \(O(n)\).

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define i128 __int128
using namespace std;
const int N = 5005;
LL n,T,t[N],c[N],dp[N];deque<LL> q;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool DuocChon(LL a1,LL a2,LL k){
    return (dp[a2]-dp[a1]<=k*(c[a2]-c[a1]));
}
bool KhongHopLe(LL a1,LL a2,LL a3){
    LL Lx=(dp[a2]-dp[a1])*(c[a3]-c[a2]);
    LL Rx=(dp[a3]-dp[a2])*(c[a2]-c[a1]);
    return (Lx>=Rx);
}
int main(){
    n=read(),T=read(),q.pb(0);
    for(int i=1;i<=n;i++){
        LL nt=read(),nc=read();
        t[i]=t[i-1]+nt,c[i]=c[i-1]+nc;
    }for(int i=1;i<=n;i++){
        while(q.size()>1&&DuocChon(q[0],q[1],t[i]+T))q.pop_front();
        dp[i]=dp[q[0]]+c[i]*t[i]+T*c[n]-c[q[0]]*(t[i]+T);
        while(q.size()>1&&KhongHopLe(q[q.size()-2],q.back(),i))q.pop_back();q.pb(i);
    }cout<<dp[n]<<"\n";
    return 0;
}

P5017 Xe Chở Hành Khách

Có \(n\) người cần đi xe từ điểm A đến điểm B, người thứ \(i\) đến điểm đón xe tại phút thứ \(t_i\). Chỉ có một xe hoạt động, nhưng sức chứa xe là vô hạn. Xe xuất phát từ điểm A, đưa người trên xe đến điểm B, rồi quay lại điểm A, một chuyến đi và về mất tổng cộng \(m\) phút (thời gian lên xuống xe được bỏ qua). Xe cần đưa tất cả mọi người đến điểm B, nếu bạn có thể sắp xếp thời gian xuất phát của xe tùy ý, hãy tìm giá trị nhỏ nhất của tổng thời gian chờ đợi của \(n\) người này.

\(1 \le n \le 500\), \(1 \le m \le 100\), \(0 \le t_i \le 4 \times 10^6\).

Xem xét trừu tượng hóa đề bài. Coi thời gian như một trục số, mỗi người tương ứng với một điểm trên trục số (có thể trùng nhau). Việc sắp xếp hoạt động của xe tương đương với việc chia trục số thành một số đoạn trái mở phải đóng, và mỗi đoạn có độ dài \(\ge m\). Tổng thời gian chờ đợi của mọi người chuyển thành tổng khoảng cách từ tất cả các điểm đến ranh phải của đoạn mà nó thuộc về.

Vậy ta có một mô hình DP, định nghĩa \(dp_i\) là tổng khoảng cách (tức là tổng thời gian chờ đợi ban đầu) nhỏ nhất khi chia đoạn trên trục số \((-\infty,i]\) và ranh phải của đoạn cuối cùng là \(i\). Rõ ràng ta có công thức chuyển trạng thái \(dp_i = \min_{j \le i-m} \{ dp_j + \sum_{j<t_k<i} (i-t_k)\}\.

Tuy nhiên, phần tổng ở phía sau khá khó tính, xem xét dùng tổng tiền tố để tối ưu. Ta có công thức mới \(dp_i = \min_{j \le i- m} \{ dp_j + (cnt_i - cnt_j) \times i - (sum_i - sum_j)\}\), trong đó \(cnt_i\) là số lượng chỉ số có giá trị \(t\) thuộc khoảng \((-\infty,i]\), và \(sum_i\) là tổng các giá trị \(t\) thuộc khoảng \((-\infty,i]\).

Vậy ta có một phương pháp \(O(\max t ^2)\), hoàn toàn không thể chấp nhận được với phạm vi dữ liệu \(4 \times 10^6\).

Làm sao?Chắc là nấu ăn thôi!

Xem xét tách công thức này, ta không khó có được \(dp_i - cnt_i \times i + sum_i = - i \times cnt_j + dp_j + sum_j\), đây chính là dạng của tối ưu hệ số độ dốc. Hệ số góc \(i\) tăng đơn điệu, duy trì vỏ lồi dưới, với \(i\) thì đưa \(i-m\) vào hàng đợi để đảm bảo điểm quyết định \(j \le i-m\).

Vì mỗi trạng thái tối đa vào hàng đợi một lần, nên độ phức tạp thời gian là \(O(\max t)\), hoàn toàn có thể giải quyết.

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 5e6+5;
struct line{LL k,b;};
LL n,m,Tong,Ans,t[N];
LL cnt[N],sum[N],MxTim,dp[N],st,ed,q[N];
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
LL Tinh(LL x,LL tim){return dp[x]-tim*cnt[x];}
bool KhongHopLe(LL a1,LL a2,LL a3){
    LL Lx=(dp[a2]-dp[a1])*(cnt[a3]-cnt[a2]);
    LL Rx=(dp[a3]-dp[a2])*(cnt[a2]-cnt[a1]);
    return (Lx>=Rx);
}
int main(){
    n=read(),m=read();
    Ans=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++)
        t[i]=read()+1,MxTim=max(MxTim,t[i]),
        cnt[t[i]]++,Tong+=t[i];
    for(int i=1;i<=MxTim+m;i++)cnt[i]+=cnt[i-1];
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;st=1,ed=1,q[1]=0;
    for(int i=1;i<=MxTim+m;i++){
        if(i>m){
            while(st<ed&&KhongHopLe(q[ed-1],q[ed],i-m))ed--;
            q[++ed]=i-m;
        }while(st<ed&&Tinh(q[st],i)>=Tinh(q[st+1],i))st++;
        dp[i]=dp[q[st]]+i*(cnt[i]-cnt[q[st]]);
        if(i>=MxTim)Ans=min(Ans,dp[i]);
    }cout<<Ans-Tong<<"\n";
    return 0;
}

P2120 Xây Kho Bãi

Trên một ngọn núi có \(n\) nhà máy, nhà máy \(1\) ở đỉnh núi, nhà máy \(n\) ở chân núi. Khoảng cách từ nhà máy \(i\) đến nhà máy \(1\) là \(x_i\), và nhà máy \(i\) hiện có \(p_i\) sản phẩm hoàn thành. Hiện tại cần lưu tất cả sản phẩm của các nhà máy này vào kho, biết rằng chi phí xây kho tại vị trí nhà máy \(i\) là \(c_i\). Đối với các nhà máy không xây kho, sản phẩm chỉ có thể vận chuyển đến kho của các nhà máy có số thứ tự lớn hơn. Chi phí vận chuyển một sản phẩm đi một đơn vị khoảng cách là \(1\). Hãy giúp thiết kế phương án xây kho để tổng chi phí (chi phí xây dựng và chi phí vận chuyển) là nhỏ nhất.

\(1 \le n \le 10^6\), \(0 \le x_i,p_i,c_i < 2^{31}\).

Đặt \(dp_i\) là chi phí nhỏ nhất khi xây kho tại nhà máy \(i\) và chỉ xem xét việc lưu trữ sản phẩm của các nhà máy đầu tiên, ta có thể viết ra công thức chuyển trạng thái \(dp_i = \min_{j<i} \{ dp_j + \sum_{k=j+1}^{i} (x_i - x_k)p_k + c_i \}\), vậy ta có được một DP \(O(n^2)\).

Độ phức tạp hoàn toàn không thể chịu nổi, trước hết hãy tách công thức thành \(dp_i = \min_{j<i} \{ dp_j + \sum_{k=j+1}^{i} x_i p_k - \sum_{k=j+1}^{i} x_k p_k + c_i \}\.

Đặt \(sum_i = \sum_{k=1}^{i} x_k p_k\), \(sp_i =\sum_{k=1}^{i} p_k\), có thể đơn giản hóa thành \(dp_i = \min_{j<i} \{ dp_j + x_i(sp_i- sp_j) - (sum_i - sum_j) + c_i \}\.

Giả sử có hai vị trí \(a,b\) trước đó và \(a<b\), vậy nếu chuyển từ \(a\) sang sẽ tốt hơn \(b\), không khó thấy cần thỏa mãn \(x_i < \dfrac{(dp_b + sum_b) - (dp_a + sum_a)}{sp_b - sp_a}\. Phía bên phải này có thể coi là hệ số góc của đường thẳng nối các điểm dạng \((sp_i,dp_i + sum_i)\), vì hệ số góc cần ngày càng lớn, có thể duy trì một vỏ lồi dưới. Vậy đây chính là bài toán mẫu của tối ưu hệ số độ dốc.

Cuối cùng lưu ý rằng một số nhà máy có thể không có sản phẩm, lúc này sẽ xuất hiện trường hợp \(sp_i - sp_j = 0\) trong việc xây dựng đường thẳng, vì hai điểm có hoành độ giống nhau thì rõ ràng điểm có tung độ nhỏ hơn sẽ tốt hơn, do đó nếu \(y>0\) thì coi là dương vô cực, ngược lại thì coi là âm vô cực.

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 1e6+5;
LL n,x[N],p[N],c[N],sp[N],spx[N];
LL st,ed,q[N],dp[N],Ans;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool LaDiemToiUu(int i,int j,int k){
    LD dx=sp[i]-sp[j];
    LD dy=dp[i]+spx[i]-dp[j]-spx[j];
    return (dy/dx<=k);
}
bool SoSanhHaiDuongThang(int i,int j,int k,int l){
    LD dx=sp[i]-sp[j];
    LD dy=dp[i]+spx[i]-dp[j]-spx[j];
    LD bx=sp[k]-sp[l];
    LD by=dp[k]+spx[k]-dp[l]-spx[l];
    return (dy/dx>=by/bx);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        x[i]=read(),p[i]=read(),c[i]=read(),
        sp[i]=sp[i-1]+p[i],spx[i]=spx[i-1]+p[i]*x[i];
    st=1,ed=1,dp[0]=0,q[1]=0;
    for(int i=1;i<=n;i++){
        while(st<ed&&LaDiemToiUu(q[st],q[st+1],x[i]))st++;
        dp[i]=dp[q[st]]+c[i]+x[i]*(sp[i]-sp[q[st]])-(spx[i]-spx[q[st]]);
        if(!p[i])dp[i]=min(dp[i],dp[i-1]);
        while(st<ed&&SoSanhHaiDuongThang(q[ed-1],q[ed],q[ed-1],i))ed--;q[++ed]=i;
    }Ans=dp[n];
    for(int i=n;i&&sp[i]==sp[i-1];Ans=min(Ans,dp[--i]));
    cout<<Ans<<"\n";
    return 0;
}

Tóm tắt và Tổng kết

Tối ưu hóa Hệ số Độ dốc cho Quy hoạch Động là một kỹ thuật hiệu quả để tối ưu hóa một số dạng cụ thể của chuyển trạng thái Quy hoạch Động, thường có thể chuyển đổi độ phức tạp từ \(O(n^2)\) xuống \(O(n \log n)\). Ý tưởng cốt lõi là biến đổi công thức chuyển trạng thái của DP thành dạng đoạn chắn của đường thẳng, trừu tượng hóa mỗi trạng thái lịch sử thành một điểm trên mặt phẳng, duy trì vỏ lồi dưới hoặc vỏ lồi trên để nhanh chóng tìm ra điểm quyết định tối ưu, và sử dụng hàng đợi đơn hoặc tìm kiếm nhị phân để cập nhật và truy vấn hiệu quả. Tóm lại, đây là một phương pháp tối ưu Quy hoạch Động vừa thông minh vừa mạnh mẽ!