洛谷 P1064 [NOIP2006 提高组] 金明的预算方案 (Java 写的)

这道题重在思路，也是典型的0 1 背包问题，是背包问题的升级版

主件携带附件，在Java中很容易就想到了map结构，key是主件的id值，value是附件

当key为0时候，里面就全是主件了

同时考虑状态转移方程，考虑的情况，一共有4种

1、买主件 + 两个附件

2、买主件 + 一个附件

3、只买主件

4、什么都不买

考虑好之后可以直接上代码了，因为人是弱鸡，只会二维背包动态，代码如下

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;/*** @Author congge* @Date 2023/10/1 21:03* @description 金明的预算方案* https://www.luogu.com.cn/problem/P1064*/
public class Main {public static void main(String[] args) {Input scan = new Input();int n = scan.nextInt() / 10;int m = scan.nextInt();/*** 保留所有主键以及附件* father 为 0 的都存到了0号位当中*/HashMap> sonAndFather = new HashMap<>();/*** 初始化map*/for (int i = 0; i <= m; i++) {sonAndFather.put(i, new ArrayList<>());}/*** 键入*/for (int i = 1; i <= m; i++) {Good good = new Good();good.v = scan.nextInt() / 10;good.p = scan.nextInt() * good.v;good.father = scan.nextInt();good.idx = i;sonAndFather.get(good.father).add(good);}ArrayList fathers = sonAndFather.get(0);int M = fathers.size();/*** 这里只需要dp一下主键即可，附件附加到主键上面判断就好*/int[][] dp = new int[M][n + 1];Good father = fathers.get(0);ArrayList sonOfFather = sonAndFather.get(father.idx);/*** 表示当前主键的孩子数目*/int sonOfSize = sonOfFather.size();/*** 用于计算两个孩子的时候总的钱与价值*/int sumV;int sumP;/*** 用于计算一个孩子的时候的钱与价值*/int curSumV;int curSumP;/*** 初始化边界*/for (int j = father.v; j <= n; j++) {/*** 带两个附件的*/if (sonOfSize == 2) {sumV = father.v + sonOfFather.get(0).v + sonOfFather.get(1).v;/*** 钱大于总共的钱的时候计算*/if (j >= sumV) {sumP = father.p + sonOfFather.get(0).p + sonOfFather.get(1).p;dp[0][j] = sumP;continue;}}/*** 带一个附件的*/if (sonOfSize >= 1) {for (int k = 0; k < sonOfSize; k++) {curSumV = sonOfFather.get(k).v + father.v;/*** 这里同理*/if (j >= curSumV) {curSumP = sonOfFather.get(k).p + father.p;dp[0][j] = Math.max(dp[0][j], curSumP);}}}/*** 只有主件的情况*/sumV = father.v;if (j >= sumV) {sumP = father.p;dp[0][j] = Math.max(dp[0][j], sumP);}}for (int i = 1; i < M; i++) {father = fathers.get(i);sonOfFather = sonAndFather.get(father.idx);sonOfSize = sonOfFather.size();for (int j = 1; j <= n; j++) {/*** 带两个附件的*/if (sonOfSize == 2) {sumV = father.v + sonOfFather.get(0).v + sonOfFather.get(1).v;if (j >= sumV) {sumP = father.p + sonOfFather.get(0).p + sonOfFather.get(1).p;dp[i][j] = dp[i - 1][j - sumV] + sumP;}}/*** 带一个附件的*/if (sonOfSize >= 1) {for (int k = 0; k < sonOfSize; k++) {curSumV = sonOfFather.get(k).v + father.v;if (j >= curSumV) {curSumP = sonOfFather.get(k).p + father.p;dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - curSumV] + curSumP);}}}/*** 只有主件的情况*/if (j >= father.v) {dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - father.v] + father.p);}/*** 什么都不买的时候*/dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);}}System.out.println(dp[M - 1][n] * 10);}static class Good {int v;int p;int idx;int father;}static class Input {StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public int nextInt() {try {in.nextToken();} catch (IOException e) {e.printStackTrace();}return (int) in.nval;}}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！