AcWing 1262. 鱼塘钓鱼java
原题链接
简单
作者:
季之秋
,
2021-02-27 22:51:33
,
所有人可见
,
阅读 321
import java.util.*;
public class Main{
static int N=1010;
static int[] a=new int[N];
static int[] d=new int[N];
static int[] l=new int[N];
static int[] minute=new int[N];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i = 1;i <= n;i++) a[i]=sc.nextInt();
for(int i = 1;i <= n;i++) d[i]=sc.nextInt();
for(int i = 2;i <= n;i++){
l[i]=sc.nextInt();
l[i]+=l[i-1];
}
int T=sc.nextInt();
int res=0;
for(int i=1;i<=n;i++){
res=Math.max(res,fish(i,T-l[i]));//遍历每个方案,
}
System.out.println(res);
}
static int fish(int q,int T){
Arrays.fill(minute,0);//清空之前方案状态
int res=0;//钓鱼和
int t=1; //每分钟可以钓最多的鱼塘好
for(int i=1;i<=T;i++){
for(int j=1;j<=q;j++){
if(get(j)>get(t)) t=j;
}
res+=get(t); //T分钟在前q个鱼塘钓鱼总和
minute[t]++; //在t鱼塘钓鱼时间加1分钟 用于计算当前下一分钟的钓鱼数
}
return res;
}
static int get(int i){
return Math.max(0,a[i]-d[i]*minute[i]); //当钓鱼时间过长或d数组值很大,可能会出现负数
//可能导致最优解的res加了一个负数get(t),与答案不符,只可能出现钓不着的情况,不看钓着钓着鱼少了
}
}