P2258 子矩阵
斯德哥尔摩
2018-10-20 23:07:52
[P2258 子矩阵](https://www.luogu.org/problemnew/show/P2258)
本蒟蒻表示一眼看错了题面。。。
把子矩阵理解错了，认为是一道沙茶题。。。
然后发现，这个样例好像不对啊。。。
回头看题，我就是个$ZZ$——子矩阵：选取某些行和某些列交叉位置所组成的新矩阵。。。
坑爹无极限。。。
考虑暴力搜索，从数据规模来看可以知道时间复杂度铁定$TLE$。。。
然后从暴力的基础上优化。
我们发现我们主要是选取行和列的时候耗费了大量时间。
那么我们就考虑使用枚举行的选择情况，即类似全排列的组合情况。
确定行的选取情况后，用$dp$来求出最小的列情况。
由于$dp$和搜索本来就是差不多的东西，所以正确性可以保证。
最后扫一遍所有的$dp$值，输出最小即可。
然后这个题的关键就变成了：如何正确地$dp$。
设$dp[i][j]$代表选择了$i$列且最后一列选择原图中第$j$列的差的绝对值和的最小值。
每次利用前缀和算出每列之间的分数$w$，两列之间的分数$sum$。
转移方程长这个样：
$$dp[i][j]=\min\{dp[i-1][k]+w[j]+v[j][k]\}$$
复杂的上限是$O(C_{16}^8\times 16^3)$，可以过。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 20
using namespace std;
int n,m,r,c,ans=2147483646;
int w[MAXN],line[MAXN];
int val[MAXN][MAXN],sum[MAXN][MAXN],dp[MAXN][MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void solve(){
memset(w,0,sizeof(w));
memset(sum,0,sizeof(sum));
memset(dp,127,sizeof(dp));
for(int i=1;i<=m;i++){
for(int j=1;j<r;j++)
w[i]+=abs(val[line[j]][i]-val[line[j+1]][i]);
for(int j=i+1;j<=m;j++)
for(int k=1;k<=r;k++)
sum[i][j]+=abs(val[line[k]][i]-val[line[k]][j]);
}
dp[0][0]=0;
for(int i=1;i<=c;i++)
for(int j=i;j<=m;j++)
for(int k=0;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i-1][k]+w[j]+sum[k][j]);
for(int i=c;i<=m;i++)ans=min(ans,dp[c][i]);
}
void dfs(int x,int last){
if(x>r){
solve();
return;
}
for(int i=last+1;n-i>=r-x;i++){
line[x]=i;
dfs(x+1,i);
}
}
void work(){
dfs(1,0);
printf("%d\n",ans);
}
void init(){
n=read();m=read();r=read();c=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
val[i][j]=read();
}
int main(){
init();
work();
return 0;
}
```