A/B's Blog

NOIP2014普及 P2258:子矩阵

未分类 b-a - 1

https://www.luogu.org/problem/show?pid=2258
做法:搜索+DP..
复杂度O(2^n * n^3)
勉强能过..硬是给这题垃圾题调了几天..
[code lang=”cpp”]
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 16
#define INF 1147483646
using namespace std;
int g[MAXN][MAXN];
bool used[MAXN];
int nowr[MAXN];
int s[MAXN];
int lacol[MAXN][MAXN];
int larow[MAXN];
int f[MAXN][MAXN];
int ans = INF;
int n, m, r, c;

int abs(int a){return a > 0? a: -a;}

void _(){
int now = INF;
memset(lacol, 0, sizeof(lacol));
memset(larow, 0, sizeof(larow));
/***预处理选中行列的差***/
for (int i = 0; i < n; i++)
for (int j = i; j < m; j++)
for (int k = 0; k < r; k++){
lacol[i][j] += abs(g[nowr[k]][i] – g[nowr[k]][j]);
}
for (int j = 0; j < m; j++){
for (int k = 0; k < r – 1; k++) larow[j] += abs(g[nowr[k]][j] – g[nowr[k + 1]][j]);
f[1][j] = larow[j];
}

for (int k = 2; k <= c; k++){
for (int i = k – 1; i < m; i++){
f[k][i] = INF;
for (int j = k – 2; j < i; j++){
f[k][i] = min(f[k – 1][j] + lacol[j][i] + larow[i], f[k][i]);
}
}
}

for (int i = c; i < m; i++){
now = min(now, f[c][i]);
}
ans = min(now, ans);
}

void solve(int idx, int lay){
if (lay == r){
_();
return;
}
for (int i = idx; i < n; i++){
if (used[i] || i == -1) continue;
used[i] = 1;
nowr[lay] = i;

solve(i, lay + 1);
used[i] = 0;
}
}

int main(){
// freopen("c.txt", "w", stdout);
memset(nowr, 0, sizeof(nowr));
scanf("%d%d%d%d", &n, &m, &r, &c);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++){
scanf("%d", &g[i][j]);
}
solve(-1, 0);
printf("%d", ans);
}
[/code]

版权所有 © 呆毛 2018 ⁄ 主题 INN AO