网站的flash,有关网站排名的论文,wordpress建站邮件,免费素材图库题目#xff1a;题目链接 思路#xff1a;由于t最大值其实只有180 * 50 678#xff0c;可以直接当成01背包来做#xff0c;需要考虑的量有两个#xff0c;时间和歌曲数#xff0c;其中歌曲优先级大于时间#xff0c;于是我们将歌曲数作为背包收益#xff0c;用时间作为…题目题目链接 思路由于t最大值其实只有180 * 50 678可以直接当成01背包来做需要考虑的量有两个时间和歌曲数其中歌曲优先级大于时间于是我们将歌曲数作为背包收益用时间作为背包容量进行dp记录下最多歌曲数目最后通过最多歌曲数目得出最多歌曲数目下的最长时间利用滚动数组我们只需要开一维数组即可 AC代码 import java.util.Arrays;
import java.util.Scanner;public class Main {final public static int maxn 10000;public static void main(String[] args) {Scanner in new Scanner(System.in);int T, n, len;int[] f new int[maxn];int[] t new int[55];T in.nextInt();for(int kase 1; kase T; kase) {Arrays.fill(f, 0);n in.nextInt();len in.nextInt();for(int i 0; i n; i)t[i] in.nextInt();int _max 0;for(int i 0; i n; i) {for(int j len - 1; j t[i]; --j) {if(f[j - t[i]] 1 || j t[i]) {f[j] Math.max(f[j], f[j - t[i]] 1);_max Math.max(_max, f[j]);}}}int i;for(i len - 1; f[i] ! _max; --i);if(_max 0)System.out.format(Case %d: %d %d\n, kase, 1, 678);elseSystem.out.format(Case %d: %d %d\n, kase, _max 1, i 678);}in.close();}
} 转载于:https://www.cnblogs.com/fan-jiaming/p/10051081.html
