[POI2006]ORK-Ploughing

描述

Byteasar 想耕种他那块矩形的田,他每次能耕种矩形的一边(上下左右都行),在他每次耕完后,剩下的田也一定是矩形,每块小区域边长为 1,耕地的长宽分别为 m 和 n,不幸的是 Byteasar 只有一匹老弱的马,从马开始耕地开始,只有当它耕完了一边才会停下休息。但有些地会非常难耕以至于马会非常的累,因此Byteasar 需要特别小心。

当耕完了一边之后,马可以停下来休息恢复体力。每块地耕种的难度不一,但是 Byteasar 都非常清楚。我们将地分成 m x n 块单位矩形——我们用坐标(I,j)来定义它们。每块地都有一个整数 T[I,J],来定义(I,j)的耕种难度。所以每次马耕一边地时的难度就是所有它耕种的地的难度总和,对于这匹虚弱的马而言,这个值不能超过他的体力值HP。

Byteasar 想知道在马不死掉的情况下最少需要耕多少次才能把地耕完。

输入

第一行三个整数, HP,M,N

接下来 N 行每行 M 个整数表示难度值。(0<=难度值<=10 000)

输出

一个整数表示最少的耕种次数(保证马能耕完)。

样例

Sample Input

12 6 4

6 0 4 8 0 5

0 4 5 4 6 0

0 5 6 5 6 0

5 4 0 0 5 4

Sample Output

8

提示

1<=HP<=200 000 000,1<=m,n<=2000.

首先,如果确定了最后一次耕地是竖着耕的时候,

那么可以确定总共竖着耕了 M 次。

竖着耕的次数确定了,我们只需要使横着耕的次数最少即可。

对此,我们枚举和最后一次竖着耕的那根竖条的上端点高度,则只需要下端点尽量往下延伸。

那么我们就开始贪心。

先贪心左右竖边,能耕则耕,再贪心上横边,最后再贪心下横边,

这样的方法必是当前枚举的量中最优的。

设枚举的上端点为 L 时,贪心的下端点最下为 R。则此时的解为 m+n-(r-l+1),如果能更新答案则加入 ANS。

同理对于最后一次耕地时横着耕的情况类似(其实把图转一下再解一遍就好了)。

代码蒯上

#include<iostream>

#include<iomanip>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

inline int gotcha()

{

    register int _a=0;bool _b=1;register char _c=getchar();

    while(_c<'0' || _c>'9'){if(_c=='-')_b=0;_c=getchar();}

    while(_c>='0' && _c<='9')_a=_a*10+_c-48,_c=getchar();

    return _b?_a:-_a;

}

const int _ = 2002;

int col[_][_]={0},ver[_][_]={0},dmg[_][_]={0},tmp[_][_],m,n,HP;

int ponyvile()

{

	register int i,j,vl,vr,cl,cr,mi=2e9;

	memset(col,0,sizeof(col));memset(ver,0,sizeof(ver));

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

		for(j=1;j<=m;j++)

			col[j][i]+=col[j-1][i]+dmg[j][i],ver[j][i]+=ver[j][i-1]+dmg[j][i];

	for(i=0;i<=m;i++)

	{

		vl=1,vr=n,cl=1,cr=m;

		int ans=i+n;

		while(vl<=vr && cl<=cr)

		{

			if(col[cr][vl]-col[cl-1][vl]<=HP)vl++;

			else if(col[cr][vr]-col[cl-1][vr]<=HP)vr--;

			else if(cl<=i && ver[cl][vr]-ver[cl][vl-1]<=HP)cl++;

			else if(ver[cr][vr]-ver[cr][vl-1]<=HP)cr--,ans++;

			else{ans=2e9;break;}

		}

		mi=min(ans,mi);

	}

	return mi;

}

	#include<map>

	map<long double,int>s;

int main()

{

	register int i,j,mi=2e9;

	HP=gotcha(),m=gotcha(),n=gotcha();

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

		for(j=1;j<=m;j++)

			dmg[j][i]=tmp[i][j]=gotcha();

	mi=ponyvile();

	memset(dmg,0,sizeof(dmg));

	swap(n,m);

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

		for(j=1;j<=m;j++)

			dmg[j][i]=tmp[j][i];

	printf("%d",min(mi,ponyvile()));

	return 0;

}

巴特西

贪心 - [POI2006]ORK-Ploughing

[POI2006]ORK-Ploughing

描述

输入

输出

样例

提示

最新文章

热门文章