【USACO 2013 February Gold】分割农场

56 阅读 0 评论 37 点赞

我是靠谱客的博主标致花卷，最近开发中收集的这篇文章主要介绍【USACO 2013 February Gold】分割农场，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

农夫约翰的农场被分成了N*N(2 <= N<= 15)个方格状的小牧场，农场的四周有围栏，但是奶牛们可以在农场内自由活动。

约翰决定修建围栏将奶牛们分开，根据当地的法律，农场内的围栏必须沿水平或垂直方向穿过整个农场，但是不能从小牧场中穿过(只能沿方格的边缘)。约翰的存款最多只能修建k条围栏(1 <= K <= 2N - 2).

约翰想要修建这样的围栏：使得农场中最大的一群奶牛中的奶牛数量尽可能的小(如果两只奶牛不用翻越围栏就能相互到达，那么它们就是同一群奶牛)。告诉你每块小牧场中奶牛的数量，请帮助约翰算出他修建围栏后最大的一群奶牛中奶牛的数量。
。

Input

第一行，两个空格间隔的整数N和K
接下来是一个由整数构成的N*N的矩阵，每个整数代表了一块牧场中奶牛的数量。

Output

一个整数，表示最大牛群的最少奶牛数

Sample Input

Sample Output

Hint

围栏的修建情况如下：
1 1|2 1 1|2 ----- 2 2|4

【分析】

很容易想到的算法是DP，但是发现横向纵向都可以插入栅栏，无法表示状态和转移状态。数据范围又很小，于是我们想到，可以枚举某一方向的状态，然后再这个基础上，对另一方向进行DP。

我们枚举纵向的插入栅栏的方式(用二进制枚举)，然后预处理在这种方式下，范围为[i,j）的行数的最大连通块权值，令其为cost[i][j]。

用f[i][j]表示到j-1为止分成了i段的最优值。

得到状态转移方程： f[i][j]=min(max(f[i-1][k],cost[k][j]));

【代码】

/**********************
    ID:Ciocio
	LANG:C++
	DATE:2013-12-21
	TASK:Div Farm
**********************/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

#define MAXN 20
#define INF (1<<30)

int N,K;
int mat[MAXN][MAXN],s[MAXN],f[MAXN][MAXN],cost[MAXN][MAXN];

int _bitcnt(int x){return x?_bitcnt(x>>1)+(x&1):0;}

void _init()
{
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			scanf("%d",&mat[i][j]);
}

void _solve()
{
	int ans=INF;   //先枚举列的情况，再DP行
	for(int S=0;S<=(1<<(N-1))-1;S++)   //最多给N-1列放栅栏
	{
		int k1=_bitcnt(S);
		if(k1>K) continue;
		for(int i=1;i<=N;i++)      //预处理
		{
			memset(s,0,sizeof(s));
			for(int j=i+1;j<=N+1;j++)     //[i,j)行,注意是开区间
			{
				cost[i][j]=0;
				int temp=0;
				for(int k=1;k<=N;k++)    //对于k这一列
				{
					s[k]+=mat[j-1][k];
					temp+=s[k];           //temp为一个矩形的和
					cost[i][j]=max(cost[i][j],temp);
					if((S>>(k-1))&1) temp=0;   //如果这里有栅栏，新起一行
				}
			}
		}
		for(int i=0;i<=N;i++)
			for(int j=1;j<=N+1;j++)
				f[i][j]=INF;
		f[0][1]=0;
		for(int k2=1;k2<=N&&k1<=K-k2+1;k2++) //+1是因为：栅栏数+1为行数
		{
			for(int i=1;i<=N;i++)
				for(int j=i+1;j<=N+1;j++)      //由于是开区间，所以要到N+1
					f[k2][j]=min(f[k2][j],max(f[k2-1][i],cost[i][j]));
			ans=min(ans,f[k2][N+1]);
		}
	}
	cout<<ans<<endl;
}

int main()
{
	_init();
	_solve();
	return 0;
}