『动态规划·贪心』剪草
题目描述
数据范围
题解
我们思考一下,当结束前如果草被割了两次,其实可以将第一次留着不割,到第二次再割;因此每一草最多只会被割一次,这样才能够保证结果的最优性。
其次,若要割两个不同的草,并在不同的时间割除时,一定要先割生长速度的慢的草,再割快的草;因为在这一份间隔的时间内,生长速度快的草可以被割掉的更多。
或者有另外的一种理解方式:
- 第一种草的其实高度为,第二株草的起始高度为.它们的大小关系都不重要。
- 第一种草的生长速度是,第二株草的生长速度是令
- 假设割掉两株草的时间间隔为t。
- 若先割第一株草,割掉的草是
- 若现割第二株草,割掉的草是
- 此时一定有
综上所述,我们得到了一份贪心策略,按照值从小到大的顺序进行切割。
然后我们进行,设表示前i株草割了j株的最大切割数。
状态转移方程:
但是我们具体不知道第一天才能够完成,我们只要枚举这一个天数,用是否合法即可。
代码如下:
#include <bits/stdc++.h>
using namespace std;
int n,h;
int sum = 0;
int sgrow = 0;
int f[100][100];
struct node
{
int h,grow;
friend bool operator < (node p1, node p2)
{
return p1.grow < p2.grow;
}
} ;
node a[100];
int main(void)
{
freopen("grass.in","r",stdin);
freopen("grass.out","w",stdout);
cin>>n>>h;
for (int i=1;i<=n;++i) cin>>a[i].h ,sum += a[i].h;
for (int i=1;i<=n;++i) cin>>a[i].grow, sgrow += a[i].grow;
if (sum <= h) return puts("0"), 0;
sort(a+1,a+n+1);
//f[i][j]表示前i个草 采了j株 采掉的最多的草
memset(f,0,sizeof f);
for (int i=1;i<=n;++i)
for (int j=1;j<=i;++j)
f[i][j] = max(f[i-1][j], f[i-1][j-1]+a[i].h+a[i].grow*j);
for (int day=1;day<=n;++day)
if (sum+day*sgrow-f[n][day] <= h)
return cout<<day, 0;
return puts("-1"), 0;
}