未分类

NOIP2014普及 P2258:子矩阵

https://www.luogu.org/problem/show?pid=2258
做法:搜索+DP..
复杂度O(2^n * n^3)
勉强能过..硬是给这题垃圾题调了几天..

#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);
}

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

1 条评论

  1. 非常不错!支持一下!

Leave a Reply

Your email address will not be published. Required fields are marked *

相关推荐