正題

題目鏈接:https://www.luogu.org/problem/P2217

---

題目大意

$a?b$的矩陣，分成$n$個矩陣，求每個矩陣均方差最小，求答案。

---

解題思路

切$n?1$刀
設$f_{k,x1,y1,x2,y2}$表示矩陣$(x1,y1,x2,y2)$還剩下$k$刀時的最小均方差，$dfs$轉移即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int a,b,n; double x[12][12],f[12][12][12][12][12],ave; bool v[12][12][12][12][12]; double dfs(int dep,int x1,int y1,int x2,int y2) {if(v[dep][x1][y1][x2][y2])return f[dep][x1][y1][x2][y2];if(!dep){double ans=0;for(int i=x1;i<=x2;i++)for(int j=y1;j<=y2;j++)ans+=x[i][j];v[dep][x1][y1][x2][y2]=1;return (f[dep][x1][y1][x2][y2]=((ans-ave)*(ans-ave)));}double mins=1e9;for(int i=0;i<dep;i++){for(int j=x1;j<x2;j++)mins=min(mins,dfs(i,x1,y1,j,y2)+dfs(dep-i-1,j+1,y1,x2,y2));for(int j=y1;j<y2;j++)mins=min(mins,dfs(i,x1,y1,x2,j)+dfs(dep-i-1,x1,j+1,x2,y2));}v[dep][x1][y1][x2][y2]=1;f[dep][x1][y1][x2][y2]=mins;if(mins==0) printf("%d %d %d %d %d\n",dep,x1,y1,x2,y2);return mins; } int main() {scanf("%d%d%d",&a,&b,&n);for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)scanf("%lf",&x[i][j]),ave+=x[i][j];ave/=(double)n;dfs(n-1,1,1,a,b);printf("%.2lf",sqrt(f[n-1][1][1][a][b]/(double)n)); }

總結

以上是生活随笔為你收集整理的P2217-[HAOI2007]分割矩阵【dfs,记忆化搜索】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。