【题意】
已知：n,m,r,c,a[i][j]
（1 ≤ n ≤ 16, 1 ≤ m ≤ 16,1 ≤ a[i][j] ≤1000,1 ≤ r ≤ n, 1 ≤ c ≤ m）
条件：矩阵的分值定义为每一对相邻元素之差的绝对值之和
求：n*m的矩阵中找出r*c的子矩阵，使其分值最小
【构思】
对于一维的问题，就是只有一行，那么很好解决；
子矩阵，找r行，再找c列；
找r行，搜索，2^r；
然后对于列的处理，可以转化为一维的情况，发现也可以用DP；
所以时间复杂度为O(2^r*c*c)
【实现】
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
using namespace std;
const int N=17;
int n,m,r,c,p[N][N],v[N],f[N],res=INT_MAX,t[N],t1[N][N];
void init(void)
{
scanf("%d%d%d%d",&n,&m,&r,&c);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) scanf("%d",&p[i][j]);
}
int min(int i,int j)
{
return i<j?i:j;
}
int DP(void)
{
memset(t,0,sizeof t);
memset(t1,0,sizeof t1);
for (int i=1;i<=m;i++)
for (int j=1;j<v[0];j++) t[i]+=abs(p[v[j]][i]-p[v[j+1]][i]);
for (int i=1;i<m;i++)
for (int j=i+1;j<=m;j++)
for (int k=1;k<=v[0];k++) t1[i][j]+=abs(p[v[k]][i]-p[v[k]][j]);
for (int i=1;i<=m;i++) f[i]=t[i];
for (int i=2;i<=c;i++)
for (int j=m;j>=i;j--)
{
f[j]=INT_MAX;
for (int k=j-1;k>=i-1;k--) f[j]=min(f[j],f[k]+t1[k][j]);
f[j]+=t[j];
}
int ans=INT_MAX;
for (int i=c;i<=m;i++) ans=min(ans,f[i]);
return ans;
}
void DFS(int i,int dep)
{
if (dep==r)
{
res=min(res,DP());
return;
}
for (int j=i;j<=n-r+dep+1;j++)
{
v[++v[0]]=j;
DFS(j+1,dep+1);
v[v[0]--]=0;
}
}
void work(void)
{
DFS(1,0);
printf("%d\n",res);
}
int main(void)
{
init();
work();
return 0;
}
【回顾】
[1] 对于棋盘上的01选择问题，通常行用搜索，列用其他方法，降低时间复杂度
[2] 棋盘的问题，把二维转化为一维，这种思想可以延伸为特殊问题的普遍性，然后再把普遍性和特殊性建立一定的联系