题目链接:https://www.luogu.org/problem/show?pid=2258
题解:
这貌似是普及组的题诶
如果行和列都爆搜的话, <nobr> O(2n+m×r×c) </nobr>
剪剪枝或许可以(hhh我都不信)
枚举组合时,如果当前搜出的1的个数大于要求,剪枝;如果即使剩下的数的个数全选1也不足以凑齐要求,剪枝,然后根据数学推导(比较麻烦懒得写了)和杨辉三角大约可以推出来枚举每一个组合可以是O(1)的
即 <nobr> O(Crn×Ccm×r×c) </nobr>
正解是
套路的爆搜行DP列,F[i][j]表示选了i列最后一列是j的最优解
f[i][j]=min{f[i-1][k]+calc(j,k)}
复杂度差不多是 <nobr> O(2n×m2) </nobr>
#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