UVA - 757 Gone Fishing 贪心+枚举

题目大意：有n个湖泊，每个湖泊最初的5分钟能钓到f条鱼，每五分钟减少d条鱼，鱼的数目不能小于d也不能为负数，求在h小时能钓到的鱼的最大数目和在每个池塘带了多少分钟

解题思路：一个个枚举，如果用总时间减去到达另一个湖泊的时间的话，就表示它可以在两个湖泊随意行走了，然后在这些时间找到优解，并和前几次的最优解进行比较，就能得到结果

#include<cstdio>
#include<cstring>
const int maxn = 30 + 5;
int n, h;
int r[maxn];
struct Lake{
	int f;
	int d;
	int t;
};
Lake l1[maxn],l2[maxn],out[maxn];

int main(){
	int b = 1;
	while(scanf("%d", &n) && n) {

		if(b) 
			b = 0;
		else
			printf("\n");

		scanf("%d", &h);
		h = h * 60;
		for(int i = 0; i < n; i++)  {
			scanf("%d", &l1[i].f);
			l1[i].t = 0;
		}
		for(int i = 0; i  < n; i++)
			scanf("%d", &l1[i].d);
		for(int i = 0; i < n - 1; i++)
			scanf("%d", &r[i]);

		int max = -0x3f3f3f3f;
		int count = 0;

		for(int i = 0 ; i < n; i++) {
			int sum = 0;
			int time = h;

			for(int j = 0; j < n; j++)  {
				l2[j] = l1[j];
			}

			for(int j = 0; j < i; j++)
				time = time - 5 * r[j];
			
			while(time > 0) {
				int m = -0x3f3f3f3f;
				int s;
				for(int j = 0; j <= i; j++)
					if(l2[j].f > m ) {
						m = l2[j].f;
						s = j;
					}
				sum = sum + l2[s].f;
				if(l2[s].f - l2[s].d >= 0)
					l2[s].f = l2[s].f - l2[s].d;
				else
					l2[s].f = 0;

				l2[s].t = l2[s].t + 5;
				time = time -5;
			}
			if(sum > max) {
				max = sum;
				for(int j = 0; j < n; j++)  
					out[j] = l2[j];	
				
			}
		}
		printf("%d",out[0].t);

		for(int i = 1 ; i < n; i++)
			printf(", %d",out[i].t);
		printf("\n");
		printf("Number of fish expected: %d\n",max);
	}
	return 0;
}