題目地址：https://www.luogu.com.cn/problem/P4850
題解原地址：https://createsj.blog.luogu.org/solution-p4850
更好的閱讀體驗？不存在的！
既然大家都在用記憶化搜索，那我就來個 DP 題解吧，有了 O2 誰還會用 DP ？！
狀態轉移方程很容易推出來，設問題給出的矩陣為 \(\textbf A\)，其有一子矩陣，左上角坐標為 \((x_1,y_1)\) ，右下角坐標為 \((x_2,y_2)\) ，那么當只考慮這個子矩陣時，最優解為將該子矩陣切開后的兩個矩陣的最優解的最小值與該子矩陣的各元素之和，即
\[f_{x_1,y_1,x_2,y_2}=min_{x_1,y_1,x_2,y_2}+\sum\limits_{i=x_1}{x_2}\sum\limits_{j=y_1}^{y_2}\textbf A(i,j). \]
這個很容易用記憶化搜索實作，但應如何 DP 呢？
容易想到，我們應該列舉每個行數和列數不都為 \(1\) 的子矩陣，并保證該子矩陣的任意子矩陣都已得出最優解，為了方便實作，我們設一子矩陣左上角坐標為 \((i,j)\) ，有 \(k\) 行 \(l\) 列，那么當只考慮這個子矩陣時，最優解為
\[f_{i,j,k,l}=min_{i,j,k,l}+\sum\limits_{x=1}^k\sum\limits_{y=1}^l\textbf A(x+i,y+j). \]
這個狀態轉移方程與上面的等價，但能方便我們用 DP 實作，
至于求子矩陣各元素之和，我們可以利用前綴和的思想，用 \(sum_{i,j}\) 表示左上角坐標為 \((1,1)\) ，右下角坐標為 \((i,j)\) 的子矩陣各元素之和，那么左上角坐標為 \((i,j)\) 的 \(k\) 行 \(l\) 列的子矩陣各元素之和為
\[\sum\limits_{x=1}^k\sum\limits_{y=1}^l\textbf A(x+i,y+j)=sum_{i+k-1,j+l-1}-sum_{i+k-1,j-1}-sum_{i-1,j+l-1}+sum_{i-1,j-1}. \]
為了消去 \(-1\)，我們設一子矩陣左上角坐標為 \((i+1,j+1)\) ，有 \(k\) 行 \(l\) 列，那么當只考慮這個子矩陣時，最優解為 \(f_{i,j,k,l}\) ，
核心代碼如下：
// i,j,k,l 的意義已經說明
for(register int i,j,k=1,l,c,xs,ys,min,t;k<=n;++k)
for(l=1;l<=m;++l)
if(k!=1 || l!=1)
for(i=0,xs=n-k;i<=xs;++i)// xs 是為了限制 i，減少運算次數
for(j=0,ys=m-l;j<=ys;++j)//ys 同理
{
// min 表示將該子矩陣切開后的兩個矩陣的最優解的最小值
min=0x7fffffff;
// 橫著切
for(c=1;c<k;++c)
{
t=f[i][j][c][l]+f[i+c][j][k-c][l];
if(t<min)
min=t;
}
// 豎著切
for(c=1;c<l;++c)
{
t=f[i][j][k][c]+f[i][j+c][k][l-c];
if(t<min)
min=t;
}
// 狀態轉移方程
f[i][j][k][l]=min+sum[i+k][j+l]-sum[i+k][j]-sum[i][j+l]+sum[i][j];
}
不用開 O2 就可以過，評測記錄證明一切，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/56839.html
標籤：C++
上一篇：將陣列分成三個和相等的部分的題解
下一篇：C++之模板模式