題目描述
給出如下定義：
子矩陣：從一個矩陣當中選取某些行和某些列交叉位置所組成的新矩陣（保持行與列的相對順序）被稱為原矩陣的一個子矩陣，
例如，下面左圖中選取第222、444行和第222、444、555列交叉位置的元素得到一個2×32 \times 32×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
的其中一個2×32 \times 32×3的子矩陣是
4 7 4
8 6 9
相鄰的元素：矩陣中的某個元素與其上下左右四個元素（如果存在的話）是相鄰的，
矩陣的分值：矩陣中每一對相鄰元素之差的絕對值之和，
本題任務：給定一個nnn行mmm列的正整數矩陣，請你從這個矩陣中選出一個rrr行ccc列的子矩陣，使得這個子矩陣的分值最小，并輸出這個分值，
(本題目為2014NOIP普及T4)
輸入格式
第一行包含用空格隔開的四個整數n,m,r,cn,m,r,cn,m,r,c，意義如問題描述中所述，每兩個整數之間用一個空格隔開，
接下來的nnn行，每行包含mmm個用空格隔開的整數，用來表示問題描述中那個nnn行mmm列的矩陣，
輸出格式
一個整數，表示滿足題目描述的子矩陣的最小分值，
輸入輸出樣例
輸入 #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
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m, r, c;
int num[N][N], ch[N], gs = 1;
int lc[N], hc[N][N];
int f[N][N];
/*
具體思路：
首先想到暴力方法
列舉每個rc大小的矩陣，然后計算差值和，但復雜度過高
需要優化：
首先列舉n行中的r行
利用dfs()列舉每種可能，當dfs()進行到已經不能完成r行時停止
預處理選出來的r行每一列之間的行與行的差值和即lc[i]
在預處理c列中任意兩列之間的差值和即hc[i][j] 第i列和第j列的差值和
利用線性dp處理即可
f[i][j]表示前i列中選j列的最小值(選第j列)
f[i][j] = min(f[i][j], f[k][j - 1] + lc[i] + hc[i][k])
*/
void Init()
{
for(int i = 1; i <= m; i++)
{
lc[i] = 0;
for(int j = 1; j < r; j++)
{
lc[i] += abs(num[ch[j]][i] - num[ch[j + 1]][i]);//
}
}
for(int i = 2; i <= m; i++)
{
for(int j = 1; j < i; j++)
{
hc[i][j] = 0; //第i列減第j列的中r行的差值差值
for(int k = 1; k <= r; k++)
{
hc[i][j] += abs(num[ch[k]][i] - num[ch[k]][j]);
}
}
}
}
int minn = 2e9;
int cmin;
void dp()
{
for(int i = 1; i <= m; i++) //前i行
{
cmin = min(i, c);
for(int j = 1; j <= cmin; j++)//選j行
{
if(j == 1)
f[i][j] = lc[i];
else
{
if(i == j)
{
f[i][j] = f[i - 1][j - 1] + lc[i] + hc[i][j - 1];
}
else
{
f[i][j] = 2e8;
for(int k = j - 1; k < i; k++)
{
f[i][j] = min(f[i][j], f[k][j - 1] + lc[i] + hc[i][k]);
}
}
}
if(j == c) minn = min(minn, f[i][c]);//前i列選c列
}
}
}
void dfs(int node)
{
if(node > n)
{
Init();
dp();
return;
}
if(r - gs + 1 == n - node + 1)//已經取地行數還沒取得行數 優化剪枝
{
ch[gs ++] = node;
dfs(node + 1);
ch[gs --] = 0;
return;
}
dfs(node + 1);
if(gs <= r)
{
ch[gs ++] = node;
dfs(node + 1);
ch[gs --];
}
}
int main()
{
cout << 2<<20 << e
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", &num[i][j]);
dfs(1);
printf("%d", minn);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/179656.html
標籤：AI