问题标题: 酷町堂：DP萌新求助：3671 割韭菜（chives）爆50分

3671   割韭菜（chives）经验值：2400

题目描述 Description

酷町猫的菜园里有N颗韭菜，编号从0到N-1，酷町猫虽然自己不喜欢吃韭菜，但是会拿韭菜招待它的好朋友。每次割韭菜的目标是使得割完以后的韭菜高度之和不会超过H。在第0时刻，第i颗韭菜的高度为h[i]，接下来每个整数时刻，依次发生如下操作：

（1）每颗韭菜都长高了，第i颗韭菜长高的高度为grow[i]。

（2）酷町猫选择其中一颗韭菜，并把它割掉，割完以后这颗韭菜的高度为0。注意这颗韭菜并没有死，下一秒，它还是会长高。

（3）酷町猫计算这N颗韭菜的高度之和，如果不超过H，那么完成任务，一切结束，否则轮到下一时刻。

你的任务是计算：最早在第几时刻，酷町猫能够完成任务？如果是第0时刻，则输出0；如果无论如何都无法完成任务，则输出-1。

输入描述 Input Description

第一行，两个整数N和H。
第二行，N个整数，表示h[i]。
第三行，N个整数，表示grow[i]。

输出描述 Output Description

一个整数，最早完成时刻或者-1。

样例输入 Sample Input

【样例输入1】 3 16 5 8 58 2 1 1 【样例输入2】 2 58 5 8 2 1 【样例输入3】 2 0 5 8 2 1

样例输出 Sample Output

【样例输出1】 1 【样例输出2】 0 【样例输出3】 -1

数据范围及提示 Data Size & Hint

【数据范围】
对于20%的数据：1 ≤ N ≤ 7。
对于100%的数据：1 ≤ N ≤ 50，0 ≤ H ≤ 1000000，0 ≤ h[i] ≤ 100000，1 ≤ grow[i] ≤ 100000。

【样例说明1】
到了第1时刻，三棵韭菜的高度依次是7,9,59。如果酷町猫把高度是59的韭菜割掉，那么三棵韭菜高度是7+9+0=16,任务完成。

【样例说明2】
5+8=13，而13<58，所以第0时刻就是满足任务要求了。

【样例说明3】
因为任务要求是所有的韭菜高度之和小于等于0，而每次割完一颗韭菜之后都会有韭菜长高，所以永远不会满足这个要求。

#include <cstdio>
#include <cstring>
#include <iostream>
#define inf 1000005

using namespace std;

int n, H, grow[55], h[55], dp[inf], last[55];

int main() {
	memset(dp, 0x3f, sizeof(dp));
	scanf("%d %d", &n, &H);
	int h_sum = 0, grow_sum = 0; 
	for(int i=1; i<=n; i++) {
		scanf("%d", &h[i]);
		h_sum += h[i];
	}
	memcpy(last, h, sizeof(h) + 1);
	for(int i=1; i<=n; i++) {
		scanf("%d", &grow[i]);
		grow_sum += grow[i];
	}
	dp[0] = h_sum;
	if(dp[0] <= H) {
		printf("0\n");
		return 0;
	}
	int i;
	for(i=1; i<=inf; i++) {
		int pos;
		for(int j=1; j<=n; j++) {
			if(dp[i-1] + grow_sum - grow[j] - last[j] < dp[i]) {
				dp[i] = dp[i-1] + grow_sum - grow[j] - last[j];
				pos = j;
			}
		}
		for(int j=1; j<=n; j++) {
			if(j != pos) last[j]  = last[j] + grow[j];
			else last[j] = 0;
		}
		if(dp[i] <= H) {
			break;
		}
	}
	if(i>=inf) printf("-1\n");
	else printf("%d\n", i);
	return 0;
}

点我看题

周琪岳在2021-02-13 10:54:06追加了内容

顶

周琪岳在2021-02-14 10:57:10追加了内容

50分

周琪岳在2021-02-14 12:09:33追加了内容

D

周琪岳在2021-02-15 12:25:33追加了内容

我顶