前 \(k\) 優(yōu)化問題

shopping plan.

article

article

主要探討關(guān)于「求前 \(k\) 最優(yōu)解」的問題。

原理類似于 \(Dijkstra\) 的堆優(yōu)化，就我們一般可以輕松找到最小狀態(tài)，然后從最小狀態(tài)開始，重復(fù)地把常數(shù)個(gè)后繼狀態(tài)壓入堆中，然后取出堆頂作為新的最小狀態(tài)，直到 \(k\) 個(gè)狀態(tài)被取出。

而最主要的問題是：

• 每個(gè)狀態(tài)都能通過該拓展方式得到，即最后是能不漏的將所有狀態(tài)拓展到的。
• 從當(dāng)前狀態(tài)拓展到后繼狀態(tài)時(shí)，權(quán)值（或者狀態(tài)的答案）要單調(diào)（就像普通的 \(dij\) 不能跑有負(fù)權(quán)的圖一樣）。
• 每個(gè)狀態(tài)可能被重復(fù)到達(dá)，我們需要一個(gè)方法去重，一般可以在拓展時(shí)加欽定使得每個(gè)狀態(tài)的到達(dá)方法是唯一的，或者手動(dòng)去重。

Shopping Plans on Multiset

• 給定一個(gè)可重集 \(S\)，定義他的一個(gè)子集 \(T\) 是合法的，當(dāng)且僅當(dāng) \(|T|\in [l,r]\)，求出前 \(k\) 小的合法「子集和」。

  \(|S|\leq 2\times 10^5,V\leq 10^9\)。

可以先考慮當(dāng) \(l=r\) 時(shí)怎么做，顯然先將 \(S\) 從小到大排序，那么最左的 \(l\) 個(gè)數(shù)是最小的。

考慮構(gòu)造一種拓展方式能不漏的覆蓋所有狀態(tài)，對(duì)于一個(gè)的合法的狀態(tài)，我們可以將最左的可以向右移動(dòng)的數(shù)向右移動(dòng)若干位，但是不能跨越已選的數(shù)，這樣顯然覆蓋了所有狀態(tài)而且還滿足每種狀態(tài)的到達(dá)方法是唯一的，即滿足不重不漏。

但是這樣每次拓展是 \(O(n)\) 級(jí)別的，我們需要常數(shù)級(jí)的，那么我們可以欽定他每次只移一位。

那么怎么記錄狀態(tài)呢，樸素的想，可以用二進(jìn)制，但是顯然不對(duì)且無法優(yōu)化，那么我們可以定義 \((sum,i,j,k)\)，表示現(xiàn)在移動(dòng)的值位置是 \(j\)，他后面那個(gè)選擇的數(shù)在 \(k\)，前面的在 \(i\)（顯然根據(jù)定義，\(1-i\) 連續(xù)），當(dāng)前狀態(tài)和為 \(sum\)。

那么轉(zhuǎn)移有兩種：

• 將當(dāng)前移動(dòng)的數(shù)再往后移一位，顯然這需要 \(j+1<k\)，即 \((sum,i,j,k)\to (sum+a[j+1]-a[j],i,j+1,k)\)。
• 將當(dāng)前移動(dòng)的數(shù)確定下來，移動(dòng)的數(shù)變?yōu)榍耙粋€(gè)，即 \((sum,i,j,k)\to (sum,i-1,i,j)\)，然后你就發(fā)現(xiàn)當(dāng)前的狀態(tài)會(huì)被重復(fù)計(jì)算，那我們只好強(qiáng)制給前面那個(gè)數(shù)移一位了，即 \((sum,i,j,k)\to (sum+s[i+1]-s[i],i-1,i+1,j)\)，限制為 \(i+1<j\ \&\ i>0\)。

初始化很顯然選最左的 \(l\) 個(gè)數(shù)是最小的，即 \((\sum_{i=1}^l a_i,l-1,l,n+1)\)。

但是啊，就有一個(gè)問題了，我們一種方案（決策）確實(shí)可以對(duì)應(yīng)唯一的狀態(tài)，但是我們的狀態(tài)并不能對(duì)應(yīng)唯一的方案啊。

比如 \((sum,5,8,10)\)，實(shí)際上可能是選了 \((3,4,5,8,10,11)\) 也可能是 \((3,4,5,8,10,13)\)。

事實(shí)上，我們前面強(qiáng)調(diào)了每種決策由唯一的拓展路徑到達(dá)，所以并不會(huì)導(dǎo)致重復(fù)，所以通過這個(gè)可以注意到，我們的狀態(tài)并不像有一些的 dp 一樣，一種決策對(duì)應(yīng)唯一的狀態(tài)，一種狀態(tài)也對(duì)應(yīng)唯一的決策，而是決策能對(duì)應(yīng)唯一的狀態(tài)，而狀態(tài)并不能對(duì)應(yīng)唯一的決策。

那么對(duì)于 \(l\neq r\) 的情況，我們直接令初始狀態(tài)變?yōu)?\(r-l+1\) 個(gè)，將所有長(zhǎng)度的最優(yōu)都加進(jìn)去即可。

Shopping Plans on Arrays

• 給定 \(n\) 個(gè)數(shù)組，要求每個(gè)數(shù)組中恰好選一個(gè)數(shù)，求前 \(k\) 小的方案。

  \(n,k,\sum len\leq 10^5,V\leq 10^9\)。

其實(shí)類似上面，本質(zhì)上就是要構(gòu)造出一個(gè)方法使得每種決策被不重不漏的覆蓋的一個(gè)小根堆。

顯然首先給每個(gè)數(shù)組內(nèi)部從小到大排序，我們考慮按順序確定選什么。

比如我們可以定義狀態(tài) \((sum,i,j)\) 表示確定了前 \(i-1\) 行，第 \(i\) 行選第 \(j\) 個(gè)，且 \(i+1\cdots n\) 行默認(rèn)選第一個(gè)的和是 \(sum\)。

轉(zhuǎn)移：

• 第 \(i\) 行換成選第 \(j+1\) 個(gè)，\((sum,i,j)\to (sum+a[i][j+1]-a[i][j],i,j+1)\)。
• 確定了第 \(i\) 行就選 \(j\)，換到下一行，\((sum,i,j)\to (sum,i+1,1)\)。

但是這樣的狀態(tài)問題多多啊，雖然確實(shí)不漏，但是會(huì)算重復(fù)。

比如一種決策 \((1,3,2,1,1)\) 可以表示為 \((?,3,2)/(?,4,1)/(?,5,1)\)。

針對(duì)這個(gè)，我們可以先默認(rèn)每行的第一個(gè)被選，然后將 \((sum,i,1)\) 這種狀態(tài)去掉，轉(zhuǎn)移到下一行時(shí)就直接 \((sum,i,j)\to (sum+?,i+1,2)\)。

那么決策 \((1,3,2,1,1)\) 就只能表示為 \((?,3,2)\) 了，但是誒，這么改又導(dǎo)致漏掉了一些決策，比如 \((1,1,2)\)，你從第二行轉(zhuǎn)移到第三行時(shí)，根本就沒有從 \((sum,2,1)\to (sum,3,2)\) 的情況啊，那么就特殊處理一下這個(gè)情況，當(dāng) \(j=2\) 時(shí)，轉(zhuǎn)移加一個(gè) \((sum,i,2)\to (sum+(a[i][1]-a[i][2])+(a[i+1][2]-a[i+1][1]),i+1,2)\)。

但是 \(a[i][1]-a[i][2]\) 是負(fù)數(shù)啊，我們要求代價(jià)要遞增啊，也就是說，我們需要滿足 \((a[i][1]-a[i][2])+(a[i+1][2]-a[i+1][1])\geq 0\)，整理一下，即 \(a[i+1][2]-a[i+1][1]\geq a[i][2]-a[i][1]\)。

那么我們將這 \(n\) 個(gè)數(shù)組按 \(a[i][2]-a[i][1]\) 升序排序即可。

什么，你說有數(shù)組就一個(gè)數(shù)，那單領(lǐng)出來即可。

復(fù)雜度 \(O(k\log n)\)。

Shopping Plans

• 給定 \(n\) 個(gè)數(shù)組，每個(gè)數(shù)組選的數(shù)的個(gè)數(shù)必須位于 \([l_i,r_i]\)，求前 \(k\) 小的方案，沒有輸出 \(-1\)。

其實(shí)就是上面兩個(gè)東西套起來，每個(gè)數(shù)組看成一個(gè)黑盒，里面按照 Shopping Plans on Multiset 得到新的合法方案，外層套 Shopping Plans on Arrays，動(dòng)態(tài)記算，外層需要數(shù)時(shí)再讓內(nèi)層算即可。

PS：

• \(l=0\) 時(shí)，要將 \(0\) 加入答案，再將 \(l=1\)。

• \(l=r=0\) 的情況，理性特判。

• 狀態(tài)轉(zhuǎn)移時(shí)的各種邊界。

• ans=A1,Q.push((Node2){ans+a[1].y[2]-a[1].y[1],1,2}); A1 為那些只有一種選擇方案的行的和