题目
Description
有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，否则输出一个最早的完成时刻。 ## Input
第一行，两个整数N和H。
第二行，N个整数，表示h[i]。0 ≤ h[i] ≤ 100000。
第三行，N个整数，表示grow[i]。1 ≤ grow[i] ≤ 100000。
1 ≤ N ≤ 50，0 ≤ H ≤ 1000000。 ## Output
一个整数，最早完成时刻或-1。 # 题解 我恨DP...
首先可以想到只有最后一次修剪才有用，因为如果说你在前面剪了它，后来又长到你不得不剪的高度，这时候你再剪它，还不如只剪它这一次，所以剪的次数不超过N
然后可以稍微贪心一下，按照生长速度排个序
然后得到转移方程
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <bits/stdc++.h>
using namespace std;
struct grass {
int height,grow;
inline bool operator < (const grass &n) const {
return (this->grow < n.grow) || ((this->grow == n.grow) && (this->height > n.height));
}
};
int n, h, ans(107), f[107][107], sum_height, sum_grow;
grass s[107];
int main(int argc, char **argv) {
memset(f, 127, sizeof(f));
scanf("%d%d", &n, &h);
for (register int i(1); i <= n; ++i) scanf("%d", &s[i].height), sum_height += s[i].height;
for (register int i(1); i <= n; ++i) scanf("%d", &s[i].grow), sum_grow += s[i].grow;
sort(s + 1, s + 1 + n);
f[0][0] = sum_height;
for (register int i(1); i <= n; ++i) {
for (register int j(i - 1); j >= 0; --j) {
for (register int k(0); k <= j; ++k) {
f[i][k + 1] = min(f[i][k + 1],f[j][k] + sum_grow - (k + 1) * s[i].grow - s[i].height);
if (f[i][k + 1] <= h) ans = min(ans, k + 1);
}
}
}
printf("%d\n", ans == 107 ? -1 : ans);
}
|
其他
DP太难了，我都不信这是给普及组做的