import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
/**
* poj1042 枚举+贪心算法
* @author NC
*/
public class Poj1042 {
public static void main(String[] args) {
Scanner scan = new Scanner(new BufferedInputStream(System.in));
while (scan.hasNext()) {
//输入
int n = scan.nextInt();
if (n == 0) {
break;
}
int h = scan.nextInt();
h = h * 12;//以5分钟为一个时间单位
int[] fish = new int[n];
int[] decrease = new int[n];
int[] interval = new int[n];
for (int i = 0; i < n; i++) {
fish[i] = scan.nextInt();
}
for (int i = 0; i < n; i++) {
decrease[i] = scan.nextInt();
}
interval[0] = 0;//interval[i]表示以第i个湖为终点时所花路程时间
for (int i = 1; i < n; i++) {
interval[i] = scan.nextInt() + interval[i - 1];
}
//先确定是以哪一个湖为终点,枚举求出最大的
//以第一个湖为终点
int[] maxResult = new int[n];
int max = maxFish(h, Arrays.copyOf(fish, 1), decrease, maxResult);
for (int i = 1; i < n; i++) {
if (h <= interval[i]) {
break;//时间不够,无法再走远了
}
//以第i个湖为终点
int[] result = new int[n];
int m = maxFish(h - interval[i], Arrays.copyOf(fish, i + 1), decrease, result);
if (m > max) {
max = m;
maxResult = Arrays.copyOf(result, result.length);
}
}
//输出结果
for (int i = 0; i < maxResult.length; i++) {
if (i > 0) {
System.out.print(", ");
}
System.out.print(maxResult[i] * 5);
}
System.out.println("");
System.out.println("Number of fish expected: " + max);
System.out.println("");
}
}
public static int maxFish(int time, int[] fish, int[] decrease, int[] result) {
int maxNumber = 0;
while (time > 0) {
int max = fish[0];
int maxIndex = 0;
for (int i = 1; i < fish.length; i++) {
if (fish[i] > max) {
max = fish[i];
maxIndex = i;
}
}
fish[maxIndex] -= decrease[maxIndex];//鱼每一个时间单位相应减少
if (fish[maxIndex] < 0) {
fish[maxIndex] = 0;//湖里的鱼是没有负数的
}
result[maxIndex]++;
maxNumber += max;
time--;
}
return maxNumber;
}
}
#include <stdio.h>
#include <memory.h>
//改成了c语言版的
void copy(int a[], int length, int b[]) {
int i = 0;
for (i = 0; i < length; i++) {
b[i] = a[i];
}
}
int maxFish(int end, int time, int fish[], int decrease[], int result[]) {
int i, maxNumber = 0, max, maxIndex;
while (time > 0) {
max = fish[0];
maxIndex = 0;
for (i = 1; i < end; i++) {
if (fish[i] > max) {
max = fish[i];
maxIndex = i;
}
}
fish[maxIndex] -= decrease[maxIndex]; //鱼每一个时间单位相应减少
if (fish[maxIndex] < 0) {
fish[maxIndex] = 0; //湖里的鱼是没有负数的
}
result[maxIndex]++;
maxNumber += max;
time--;
}
return maxNumber;
}
int main() {
int n, h, i;
int fish[25] = {0}, decrease[25] = {0}, interval[25] = {0}, maxResult[25] = {0}, temp[25] = {0}, result[25] = {0};
while (scanf("%d", &n) && n != 0) {
memset(fish, 0, sizeof (fish));
memset(decrease, 0, sizeof (decrease));
memset(interval, 0, sizeof (interval));
memset(maxResult, 0, sizeof (maxResult));
memset(interval, 0, sizeof (interval));
//输入
scanf("%d", &h);
h = h * 12; //以5分钟为一个时间单位
for (i = 0; i < n; i++) {
scanf("%d", &fish[i]);
}
for (i = 0; i < n; i++) {
scanf("%d", &decrease[i]);
}
interval[0] = 0; //interval[i]表示以第i个湖为终点时所花路程时间
for (i = 1; i < n; i++) {
scanf("%d", &interval[i]);
interval[i] += interval[i - 1];
}
//先确定是以哪一个湖为终点,枚举求出最大的
//以第一个湖为终点
copy(fish, 1, temp);
int max = maxFish(1, h, temp, decrease, maxResult);
for (int i = 1; i < n; i++) {
if (h <= interval[i]) {
break; //时间不够,无法再走远了
}
//以第i个湖为终点
memset(result, 0, sizeof (result));
copy(fish, i + 1, temp);
int m = maxFish(i + 1, h - interval[i], temp, decrease, result);
if (m > max) {
max = m;
memset(maxResult, 0, sizeof (maxResult));
copy(result, i + 1, maxResult);
}
}
//输出结果
for (i = 0; i < n; i++) {
if (i > 0) {
printf(", ");
}
printf("%d", maxResult[i] * 5);
}
printf("\n");
printf("Number of fish expected: %d", max);
printf("\n");
printf("\n");
}
return 1;
}
分享到:
相关推荐
(poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)……中级有:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,...
(2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短...
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习
一.基本算法:枚举. (poj1753,poj2965)贪心(poj1328,poj2109,poj2586)递归和分治法
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
Algorithm-Java Algorithms + Data Structures = Programs....最短路径(dijkstra,bellman-ford,floyd,heap+dijkstra)(,,poj1062,poj2253,poj1125,poj2240) 最小生成树(prim,kruskal)(p
AlgoHub囊括了 POJ, ZOJ, leetcode, HackerRank 等网站的经典题目(一些质量不高的题目则忽略),且 AlgoHub有非常简单的加题系统,用户不需要写一行代码即可自己添加题目,所以AlgoHub的题库还在飞速增长中。...
3.贪心 4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya 定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 1、 排序 2、 搜索、...
贪心法 2.2.1 硬币问题 2.2.2 区间问题 2.2.3 字典序最小问题 2.2.4 其他例题 2.3 记录结果再利用的“动态规划” 2.3.1 记忆化搜索与动态规划 2.3.2 进一步探讨递推关系 2.3.3 有关计数问题的DP 2.4 加工并存储数据...
#POJ 题集 数论 欧几里得/拓展欧几里得算法 1006 1061 搜索 普通搜索 1062, 1088, 2386 剪枝优化 1011 动态规划 背包 1014 高精度 加减乘除 1001 巧妙处理 思维处理 1852 模拟 1017 简单题 水题 1004 1007 1008 枚举...