4.27华为机试(求大佬交流一下)
1.买水果的最佳方案
题目描述:1-n小时内,有m家水果店会在不同的时间段内售卖不同价格的水果。公司需要在每个小时都需要购买水果,求买水果最便宜的方案。
思路:就是一个区间修改,单点查询的题。一开始就在想不会让写线段树吧,但是先写了暴力,结果只过了30多,我就开始写线段树了,结果也没写对。
最后在别的帖子里看到初始值设为Integer.MAX_VALUE,暴力就能100%了。题目给的1000,我设的1001,这都能骗人的吗?我真的服了呀,哈哈哈哈哈哈哈
2.修正算数公式
这道题没写,详情可以看这里 ,还有大佬的思路
3.团队能完成的项目最大价值
题目描述:有3个团队,每个团人都有一定的人数。有m个项目,给出每个项目分别需要各个团队多少人以及每个项目的价值。求团队能完成的项目最大价值
思路:一下子就想到了背包,但是容量有3个维度,我在想是多重背包吗?本质也就是0-1背包,三下五除二写完了,结果就只过18%。不知道是状态定义错了还是转移方程错了,最后也没改出来。
下面给我的错误代码,求大佬交流
// s1,s2,s3分别表示3个团队的人力数 int[][][] dp = new int[s1+1][s2+1][s3+1] // 项目价值 int[] val = new int[m]; // 项目需要人力数 int[][] need = new int[m][3]; for(int i=1;i<=m;++i){ for(int j=s1;j>=need[i-1][0];--j){ for(int k=s2;k>=need[i-1][1];--k){ for(int x=s3;x>=need[i-1][2];--x){ dp[j][k][x] = Math.max(dp[j][k][x],dp[s1-j][s2-k][s3-x] + val[i-1]); } } } } return dp[s1][s2][s3];#华为机试##笔试题目##笔试题型##华为#