题目

有N棵小草，编号0至N-1。奶牛Bessie不喜欢小草，所以Bessie要用剪刀剪草，目标是使得这N棵小草的高度总和不超过H。在第0时刻，第i棵小草的高度是h[i]，接下来的每个整数时刻，会依次发生如下三个步骤：

（1）每棵小草都长高了，第i棵小草长高的高度是grow[i]。

（2）Bessie选择其中一棵小草并把它剪平，这棵小草高度变为0。注意：这棵小草并没有死掉，它下一秒还会生长的。

（3）Bessie计算一下这N棵小草的高度总和，如果不超过H，则完成任务，一切结束，否则轮到下一时刻。

你的任务是计算：最早是第几时刻，奶牛Bessie能完成它的任务？如果第0时刻就可以完成就输出0，如果永远不可能完成，输出-1，否则输出一个最早的完成时刻。

分析

首先分析的出两个结论，

1、每棵草最多只剪一次

2、按照生长速度，先剪小的，再剪大的。

不难证明，略。

那么把小草按生长速度从大到小排个序后，

设\(f_{i,j}\)表示，在倒数第i个时刻，已经处理了j棵草时的最小高度和。

转移为\(f[i][j]=min(f[i][j-1],f[i-1][j-1]-a[j].g*(ans-i+1)-a[j].h)\)

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const long long maxlongint=2147483647;

const long long mo=1000000007;

const long long N=55;

using namespace std;

long long f[N][N],n,m,ans;

struct ddx

{

	long long g,h;

}a[N];

bool cmp(ddx x,ddx y)

{

	return x.g>y.g;

}

int main()

{

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

	long long sum1=0,sum=0;

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

	{

		scanf("%lld",&a[i].h);

		sum1+=a[i].h;

	}

	if(sum1<=m)

	{

		printf("0");

		return 0;

	}

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

	{

		scanf("%lld",&a[i].g);

		sum+=a[i].g;

	}

	sort(a+1,a+1+n,cmp);

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

	{

		memset(f,43,sizeof(f));

		for(int i=0;i<=n;i++) f[0][i]=sum1+ans*sum;

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

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

			{

				f[i][j]=min(f[i][j-1],f[i-1][j-1]-a[j].g*(ans-i+1)-a[j].h);

				if(f[i][j]<=m)

				{

					printf("%d",ans);

					return 0;

				}

			}

	}

	printf("-1");

}

巴特西

【NOIP2012模拟10.25】剪草

题目

分析

最新文章

热门文章