luogu2258

题面

sol：先爆搜搜出r行，再在那r行中选c列DP得到最优解

我太菜了，这种题都做了好久，还需锻炼码力啊qwq

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, r, c, Map[20][20], loc[20], ll[20], hh[20][20], f[20][20], ans;
inline void solve()
{
    memset(f, 127, sizeof f);
    memset(ll, 0, sizeof ll);
    memset(hh, 0, sizeof hh);
    for(int i = 1; i <= m; i++)
    for(int j = 2; j <= r; j++)
    ll[i] += abs(Map[loc[j]][i] - Map[loc[j - 1]][i]);
    for(int i = 1; i <= m; i++)
    for(int j = i + 1; j <= m; j++)
    for(int k = 1; k <= r; k++)
    hh[i][j] += abs(Map[loc[k]][i] - Map[loc[k]][j]);
    for(int i = 1; i <= m; i++)
    f[1][i] = ll[i];
    for(int i = 1; i <= c; i++)
    for(int j = 1; j <= m; j++)
    for(int k = j + 1; k <= m ; k++)
    f[i][k] = min(f[i][k], f[i - 1][j] + ll[k] + hh[j][k]);
    for(int i = c; i <= m; i++)
    ans = min(ans, f[c][i]);
}
inline void dfs(int x, int pre)
{
    if (x == r + 1)
    {
        solve();
        return;
    }
    for(int i = pre + 1; n - i >= r - x; i++)
    loc[x] = i,
    dfs(x + 1, i);
}
int main()
{
    while(~scanf("%d%d%d%d", &n, &m, &r, &c))
    {
        ans = 0x3f3f3f3f;
        memset(loc, 0, sizeof loc);
        for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        scanf("%d", &Map[i][j]);
        dfs(1, 0);
        printf("%d
", ans);
    }
}