多路并归,贪心:《信息学奥赛一本通》：池塘钓鱼

有 N� 个鱼塘排成一排，每个鱼塘中有一定数量的鱼，例如：N=5�=5 时，如下表：

鱼塘编号	1	2	3	4	5
第1分钟能钓到的鱼的数量（1..1000）	10	14	20	16	9
每钓鱼1分钟钓鱼数的减少量（1..100)	2	4	6	5	3
当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟）	3	5	4	4

即：在第 1 个鱼塘中钓鱼第 1 分钟内可钓到 10 条鱼，第 2 分钟内只能钓到 8 条鱼，……，第 5 分钟以后再也钓不到鱼了。

从第 1 个鱼塘到第 2 个鱼塘需要 33 分钟，从第 2 个鱼塘到第 3 个鱼塘需要 5 分钟，……

给出一个截止时间 T，设计一个钓鱼方案，从第 1 个鱼塘出发，希望能钓到最多的鱼。

假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

输入格式

共 5 行，分别表示：

第 1 行为 N；

第 2 行为第 1 分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；

第 3 行为每过 1 分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；

第 4 行为当前鱼塘到下一个相邻鱼塘需要的时间；

第 5 行为截止时间 T。

输出格式

一个整数（不超过2^31−1），表示你的方案能钓到的最多的鱼。

数据范围

1≤N≤100
1≤T≤1000

输入样例：

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

输出样例：

76

 

首先通过贪心思想可以得出最优解一定是不会掉头去之前的池塘钓鱼的，然后我们只需要每次在第 i 个池塘掉了多少鱼就可以了，首先可以枚举最后到了哪个池塘 k，也就是到的终点，表示我们只在 1 到 k 个池塘掉了鱼，k-n后面的池塘不管，然后可以通过前缀和快速求出 到 k 池塘所用时间 t， 然后剩余时间 T 全是在 1 - k 池塘钓鱼的时间，所以可以通过大根堆维护 1 - k 池塘能钓的最多的鱼，但题目数据范围也不大，也可以每次枚举 1-k 池塘能掉的最多的鱼；最后循枚举余时间 T，

得到每分钟能钓的最大的鱼，计算得出 1- k 池塘能钓的最多的鱼 res，然后更新 ans。

AC code：

#include
using namespace std;
int n, ti;
int arr[1010], A[1010];
int s[1010];
int t[1010];
int ans = 0;
//priority_queue  q;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	for (int i = 1; i <= n; i++) cin >> s[i];
	for (int i = 1; i < n; i++) {
		cin >> t[i];
		t[i] = t[i - 1] + t[i];
	}
	cin >> ti;
 
	for (int i = 1; i <= n; i++) {
		int u = 0;
		for (int u = 1; u <= n; u++) A[u] = arr[u];
		int res = t[i - 1];
		int tt = ti - res;
		for (int o = 1; o <= tt; o++) {
			int mx = -1;
			int in = -1;
			for (int j = 1; j <= i; j++) {
				if (A[j] > mx) {
					mx = A[j];
					in = j;
				}
			}
			u += A[in], A[in] -= s[in];
		}
		ans = max(u, ans);
	}
	cout << ans;
 
}

我还有一个dfs的暴力思路，但样例都过不来，不知道哪里有缺陷，希望大佬指点

 

#include
using namespace std;
int n, ti;
int arr[1010], A[1010];
int s[1010];
int t[1010];
int ans = 0;
void dfs(int x, int total, int ti, int f) {
	if (ti <= 0 || f <= 0 || x > n) return;
	ans = max(ans, total);
 
 
	dfs(x, total + f, ti - 1, f - s[x]);   // 在当前池塘钓
	dfs(x + 1, total, ti - t[x], arr[x + 1]); // 直接去下一个池塘
	dfs(x + 1, total + f, ti - t[x] - 1, arr[x + 1]); //在当前池塘掉一次就去下一个池塘
 
}
 
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	for (int i = 1; i <= n; i++) cin >> s[i];
	for (int i = 1; i < n; i++) {
		cin >> t[i];
		t[i] = t[i - 1] + t[i];
	}
	cin >> ti;
	 当前池塘，当前钓鱼数，当前剩余时间，当前池塘每分钟可钓鱼数
	dfs(1, 0, ti, arr[1]);
	cout << ans;
 
}