算法
(枚举,DP,线性DP) $O(C^r_nn^3)$
当选定的行固定时,问题变成:
给定一个长度为 $m$ 的序列,从中选出一个长度为 $c$ 的子序列。序列中的每个元素均有一个分值,且任意相邻两个被选出的元素,也会产生一个分值。问:如何选择子序列可使分值之和最小。
这是一个经典的序列DP模型:
状态表示:f[i][j]
表示所有以第i
个数结尾,且长度为j
的子序列的分值之和的最小值。
状态计算:以倒数第二个数是哪个数为依据,将f[i][j]
所代表的集合分成若干类,则倒数第二个数是第k
个数的所有子序列的最小分值是 f[k][j - 1] + cost()
,其中cost
是在序列末尾加上第i
个数所产生的分值。
f[i][j]
取所有类别的最小分值即可。
由于 $n$ 较小,我们可以直接枚举行的所有选择,然后用上述做法DP即可。
时间复杂度
一共有 $n$ 行,从中选出 $r$ 行,总共有 $C^r_n$ 种选择,对于每种选择,DP的状态总共有 $O(n^2)$ 个,计算每个状态需要 $O(n)$ 的计算量,因此DP的时间复杂度是 $O(n^3)$。
所以总时间复杂度是 $O(C^r_nn^3)$。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20, INF = 1e9;
int n, m, r, c;
int matrix[N][N];
int f[N][N];
int cw[N], rw[N][N];
int q[N];
int count(int x)
{
int s = 0;
for (int i = 0; i < n; i ++ ) s += x >> i & 1;
return s;
}
int main()
{
cin >> n >> m >> r >> c;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> matrix[i][j];
int res = INF;
for (int state = 0; state < 1 << n; state ++ )
if (count(state) == r)
{
for (int i = 0, j = 0; i < n; i ++ )
if (state >> i & 1)
q[j ++ ] = i;
for (int i = 0; i < m; i ++ )
{
cw[i] = 0;
for (int j = 1; j < r; j ++ ) cw[i] += abs(matrix[q[j]][i] - matrix[q[j - 1]][i]);
}
for (int i = 0; i < m; i ++ )
for (int j = i + 1; j < m; j ++ )
{
rw[i][j] = 0;
for (int k = 0; k < r; k ++ )
rw[i][j] += abs(matrix[q[k]][i] - matrix[q[k]][j]);
}
for (int i = 0; i < m; i ++ )
{
f[i][1] = cw[i];
for (int j = 2; j <= c; j ++ )
{
f[i][j] = INF;
for (int k = 0; k < i; k ++ )
f[i][j] = min(f[i][j], f[k][j - 1] + cw[i] + rw[k][i]);
}
res = min(res, f[i][c]);
}
}
cout << res << endl;
return 0;
}
Orz
Orz
orz