【洛谷2258】子矩阵

本文主要是介绍【洛谷2258】子矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://www.luogu.org/problem/show?pid=2258
题解：
这貌似是普及组的题诶
如果行和列都爆搜的话，$O(2^{n+m}\times r\times c)$
剪剪枝或许可以（hhh我都不信）
枚举组合时，如果当前搜出的1的个数大于要求，剪枝；如果即使剩下的数的个数全选1也不足以凑齐要求，剪枝，然后根据数学推导（比较麻烦懒得写了）和杨辉三角大约可以推出来枚举每一个组合可以是O（1）的
即$O(C_{n}^r\times C_{m}^c\times r\times c)$

正解是
套路的爆搜行DP列，F[i][j]表示选了i列最后一列是j的最优解
f[i][j]=min{f[i-1][k]+calc(j,k)}
复杂度差不多是$O(2^n\times m^2)$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;const int inf=(1<<30);
int m,n,r,c,ans=inf;
int a[20][20],p[20],f[20][20],sum[20],g[20][20];void dp()
{memset(sum,0,sizeof(sum));memset(g,0,sizeof(g));memset(f,0x7f,sizeof(f));for(int i=1;i<=m;i++)for(int j=1;j<r;j++)sum[i]+=abs(a[p[j+1]][i]-a[p[j]][i]);for(int i=1;i<=m;i++)for(int j=i+1;j<=m;j++)for(int k=1;k<=r;k++)g[i][j]+=abs(a[p[k]][j]-a[p[k]][i]);for(int i=1;i<=m;i++) f[1][i]=sum[i];for(int i=1;i<=c;i++)       for(int j=1;j<=m-(c-i);j++)for(int k=0;k<=j-1;k++)f[i][j]=min(f[i][j],f[i-1][k]+sum[j]+g[k][j]);  for(int i=c;i<=m;i++)ans=min(ans,f[c][i]);           
}void dfs(int x,int y)
{if(y==r+1) {dp();return;}if(x>n) return;dfs(x+1,y); p[y]=x;dfs(x+1,y+1);
}int main()
{cin>>n>>m>>r>>c;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];dfs(1,1);printf("%d\n",ans);return 0;
}

ps：n和m输反调了半个小时，hhh

这篇关于【洛谷2258】子矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---