題3：子矩陣

【題目描述】

給出如下定義：

1.子矩陣：從一個矩陣當中選取某些行和某些列交叉位置所組成的新矩陣（保持行與列的相對順序）被稱為原矩陣的一個子矩陣。

例如，下面左圖中選取第$2、4$行和第$2、4、5$列交叉位置的元素得到一個$2?3$ 的子矩陣如右圖所示。

2.相鄰的元素：矩陣中的某個元素與其上下左右四個元素（如果存在的話）是相鄰的。

3.矩陣的分值：矩陣中每一對相鄰元素之差的絕對值之和。

本題任務：給定一個$n$行$m$列的正整數矩陣，請你從這個矩陣中選出一個$r$行$c$列的子矩陣，使得這個子矩陣的分值最小，并輸出這個分值。

【輸入】

第一行包含用空格隔開的四個整數$n，m，r，c$，意義如問題描述中所述，每兩個整數之間用一個空格隔開。

接下來的$n$行，每行包含$m$個用空格隔開的整數，用來表示問題描述中那個$n$行$m$列的矩陣。

【輸出】

輸出共$1$行，包含$1$個整數，表示滿足題目描述的子矩陣的最小分值。

【輸入樣例1】

5 5 2 3
9 3 3 3 9
9 4 8 7 4
1 7 4 6 6
6 8 5 6 9
7 4 5 6 1

【輸出樣例1】

6

【樣例 1 說明】

該矩陣中分值最小的$2$行$3$列的子矩陣由原矩陣的第$4$行、第$5$行與第$1$列、第$3$列、第$4$列交叉位置的元素組成，為$675566$
,其分值為$|6?5|+|5?6|+|7?5|+|5?6|+|6?7|+|5?5|+|6?6|=6$。

【輸入樣例2】

7 7 3 3
7 7 7 6 2 10 5
5 8 8 2 1 6 2
2 9 5 5 6 1 7
7 9 3 6 1 7 8
1 9 1 4 7 8 8
10 5 9 1 1 8 10
1 3 1 5 4 8 6

【輸出樣例2】

16

【樣例 2 說明】

該矩陣中分值最小的$3$行$3$列的子矩陣由原矩陣的第$4$行、第$5$行與第$2$列、第$6$列、第$7$列交叉位置的元素組成，選取的分值最小子矩陣為$9957888810$

【數據說明】

對于 $50\%$ 的數據，$1\le n\le 12,1\le m\le 12$, 矩陣中的每個元素$1\le a[i][j]\le 20$；

對于 $100\%$ 的數據，$1\le n\le 16,1\le m\le 16$,矩陣中的每個元素$1\le a[i][j]\le 1000,1\le r\le n,1\le c\le m$。

【代碼如下】：

#include <bits/stdc++.h>
using namespace std;
ifstream cin("submatrix.in");
ofstream cout("submatrix.ans");
const int N=30;
int a[N][N];
int n,m,r,c;
int f[N][N];
int w[N][N];
bitset<20>now;//偷懶用了bitset做狀壓。。。 
int calc(int x)//計算橫著的 第x行 
{int last=0x3f3f3f3f,ret=0;for(int i=0;i<m;i++)if(now[i]){if(last!=0x3f3f3f3f)ret+=abs(a[x][i+1]-last);last=a[x][i+1];}return ret;
}
int work(int x,int y)//x是這一行 y是上一行 
{if(y==0)return 0;int ret=0;for(int i=0;i<m;i++)if(now[i])ret+=abs(a[x][i+1]-a[y][i+1]);return ret;
}
void init()
{for(int i=1;i<=n;i++){int t1=calc(i);for(int j=i-1;j>=0;j--)w[i][j]=t1+work(i,j);}
}
void dp()
{int ans=0x3f3f3f3f;for(int s=0;s<(1<<m);s++){    now=s;if(now.count()!=c)continue;memset(f,0x3f,sizeof f);f[0][0]=0;init();for(int i=1;i<=n;i++){for(int j=1;j<=r;j++){for(int k=0;k<i;k++)f[i][j]=min(f[k][j-1]+w[i][k],f[i][j]);}ans=min(ans,f[i][r]);}}cout << ans << endl;
}
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];dp();
}