[bzoj3061][Usaco13Feb]Partitioning the Farm_动态规划

Partitioning the Farm bzoj-3061 Usaco13Feb

题目大意：给定一个n*n的方格图，用k条贯穿方格图的直线将整个方格图分割，使得每一块的权值和的最大值最小。

注释：$1\le n \le 15$，$1\le k \le 2n-2$。

想法：想到dp不难，但是我想了很久怎么dp。这里介绍一个常用的小手法：横向状压，竖着正常dp。想到这里，几乎就切了。横向二进制枚举，然后dp即可。

最后，附上丑陋的代码... ...

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int N=20;

int a[N][N],b[N][N],c[N][N];

bool ne[N];

int n,m,t;

bool check(int k,int v)

{

	int top=1,o;memset(c,0,sizeof c);

	for(int i=1;i<=n;i++)

	{

		if(i>1&&((k>>(i-2))&1))top++;

		for(int j=1;j<=n;j++)c[top][j]+=b[i][j];

	}

	if(top>m+1)

		return 0;

	o=m-top+1;

	for(int l=0,r=1;r<=n;r++)

	{

		for(int i=1;i<=top;i++)

		{

			if(c[i][r]-c[i][r-1]>v)

				return 0;

			else

			{

				if(c[i][r]-c[i][l]>v)

					l=r-1,o--;

			}

		}

	}

	if(o<0)return 0;return 1;

}

int main()

{

	int l=0,r=0,mid,ans;bool ok;

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=n;j++)scanf("%d",&a[i][j]),r+=a[i][j];

	}

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=n;j++)b[i][j]=b[i][j-1]+a[i][j];

	}

	t=(1<<(n-1));

	while(r>=l)

	{

		mid=(l+r)>>1;ok=0;

		for(int i=0;i<t;i++)

		{

			if(check(i,mid))

			{

				ok=1;

				break;

			}

		}

		if(ok)

			ans=mid,r=mid-1;

		else

			l=mid+1;

	}

	printf("%d\n",ans);

}

小结：无论是二进制枚举还是直接dp，都是普及难度，但是和到一起而且不是暴力的承接关系(Superbia_zyb)，还是值得称赞的。

巴特西

[bzoj3061][Usaco13Feb]Partitioning the Farm_动态规划_状压dp

最新文章

热门文章