LG2258 [NOIP2014 普及组] 子矩阵
给出一个矩阵，求出一个子矩阵（对应在数列上的定义为子序列，从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵保持行与列的相对顺序被称为原矩阵的一个子矩阵。）矩阵的分值为每一对相邻元素之差的绝对值之和。
给定一个 \(n\) 行 \(m\) 列的正整数矩阵，请你从这个矩阵中选出一个 \(r\) 行 \(c\) 列的子矩阵，使得这个子矩阵的分治最小，并输出这个分值。
\(1\leq r\leq n\leq 16,1\leq c\leq m\leq 16\)。
首先我们暴力枚举每一列的选取情况，一共有 \(\binom{m}{c}\) 种，最大为 \(\binom{16}{8}=12870\) 种（枚举的时候可以使用状态压缩能减小很大常数）。
然乎考虑对每行的选取状况进行 \(dp\)。定义 \(dp_{i,j}\) 为在前 \(i\) 行中选择了 \(j\) 行且第 \(i\) 行选了的方案数。 \(O(nc)\) 预处理出第 \(i\) 行内的互相相邻的数之差的绝对值之和 \(val_i\)，\(O(n^2c)\) 预处理出第 \(i\) 行和第 \(j\) 行之间相邻的数之差的绝对值之和 \(trs_{i,j}\)。于是可以得到转移
\[dp_{i,1}=val_i\\ dp_{j,k}=\min dp_{i,k-1}+val_j+trs_{i,j} \]能在 \(O(n^2r)\) 的时间内完成。
所以总的复杂度为 \(O(\binom{m}{c}(n^2(r+c)+nc))\) 最大为 \(56010240\)，可以轻松通过。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int>ttfa;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
const int N=16,INF=0x3f3f3f3f;
int n,m,r,c,a[N][N];
int lis[1<<N],tot,dp[N][N+1],ans=INF,trans[N][N],val[N];
int main(){
n=read(),m=read(),r=read(),c=read();
for(int i=0;i<n;++i){
for(int j=0;j<m;++j)
a[i][j]=read();
}
for(int i=0;i<(1<<m);++i){
int cnt=0;
for(int j=0;j<m;++j)
if((i>>j)&1)++cnt;
if(cnt==c)lis[tot++]=i;
}
for(int l=0;l<tot;++l){
int sta=lis[l],top=0,opt[N];
memset(dp,0x3f,sizeof(dp));
//memset(opt,0x3f,sizeof(int)*c);
for(int j=0;j<m;++j)
if((sta>>j)&1)opt[top++]=j;
for(int i=0;i<n;++i){
val[i]=0;
for(int j=0;j<c-1;++j)
val[i]+=abs(a[i][opt[j]]-a[i][opt[j+1]]);
}
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
int tmp=0;
for(int k=0;k<c;++k)
tmp+=abs(a[j][opt[k]]-a[i][opt[k]]);
trans[i][j]=tmp;
}
}
for(int i=0;i<n;++i){
dp[i][1]=min(dp[i][1],val[i]);
for(int j=i+1;j<n;++j){
for(int k=2;k<=r;++k)
dp[j][k]=min(dp[j][k],dp[i][k-1]+val[j]+trans[i][j]);
}
}
for(int i=0;i<n;++i)
ans=min(ans,dp[i][r]);
}
printf("%d\n",ans);
return 0;
}