原題鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1011
題目名稱：星艦部隊(duì)
問題描述：
作為星河戰(zhàn)隊(duì)的領(lǐng)導(dǎo)者，你被派去摧毀這些蟲子的基地。
基地為一個(gè)個(gè)房間連成的樹形結(jié)構(gòu)，每個(gè)房間都被一些蟲子占據(jù)，里面也對(duì)應(yīng)一定的大腦在房間里。
你必須在每個(gè)房間留下一些士兵來對(duì)抗里面的所有蟲子。一個(gè)星艦士兵可以對(duì)抗20個(gè)蟲子。
由于你沒有足夠的士兵，你只能清理一些房間，讓神經(jīng)氣體完成其余的工作（無法獲得大腦）。
計(jì)算最大所有可獲得大腦的總和。
輸入項(xiàng)：
輸入包含多個(gè)測(cè)試用例。
從第一行開始，n m分別表示房間個(gè)數(shù)和士兵數(shù)。
接下來n行中每行為a b分別表示房間內(nèi)的蟲子數(shù)和大腦數(shù)
接下來的n-1行中每行為x y分別為表示房間連接情況，房間為樹形連接，且無法退回
然后接著是下一個(gè)測(cè)試用例，直到-1 -1表示結(jié)束
輸出項(xiàng)：
每一個(gè)測(cè)試用例可以捕獲的大腦總數(shù)
解題技巧：
背包算法（參考ACM課本98頁0-1背包），士兵是動(dòng)態(tài)變多的，問題是從最后一個(gè)往上考慮的
測(cè)試用例：
5 10
50 10
40 10
40 20
65 30
70 30
1 2
2 4
1 3
2 5
1 1
20 7
-1 -1
輸出結(jié)果：
50
7

import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Hdu1011 {//每一次任務(wù)的前提所給信息static ArrayList<Integer> roomsList[];//這是一個(gè)List的數(shù)組 每一個(gè)數(shù)組中存儲(chǔ)static int n, m;//n表示房間個(gè)數(shù)，m表示士兵個(gè)數(shù)static int bugs_brains[][];//房間的蟲子數(shù)和大腦的數(shù)量static int dp[][];//dp[i][j]表示第i個(gè)洞消耗j個(gè)士兵的獲得值static boolean vis[];//標(biāo)記本節(jié)點(diǎn)是否被遍歷過public static void main(String[] args) {List<Hdu1011DataStructure> hdu1011DataStructureList = read();//讀取輸入的內(nèi)容for (Hdu1011DataStructure hdu1011DataStructure : hdu1011DataStructureList) {System.out.println(count(hdu1011DataStructure));//對(duì)每次任務(wù)計(jì)算并輸出最終結(jié)果}}//單個(gè)準(zhǔn)備工作static int count(Hdu1011DataStructure hdu1011DataStructure) {m = hdu1011DataStructure.getM();if (m == 0) {//表示一開始就沒有士兵return 0;}n = hdu1011DataStructure.getN();vis = new boolean[n + 1];//默認(rèn)初始值為falsedp = new int[n + 1][m + 1];//初始值都為0roomsList = hdu1011DataStructure.getRooms();bugs_brains = hdu1011DataStructure.getBugs_brains();//單個(gè)準(zhǔn)備工作完畢dfs_dp(1);//從1開始return dp[1][m];}static void dfs_dp(int a) {//a表示節(jié)點(diǎn)編號(hào)vis[a] = true;//標(biāo)記本節(jié)點(diǎn)已經(jīng)遍歷了int temp = (bugs_brains[a][0] + 19) / 20;//本節(jié)點(diǎn)需要的士兵for (int i = temp; i <= m; i++)//在dp的第a行temp之后的內(nèi)容都存放可以獲得的大腦數(shù)量dp[a][i] = bugs_brains[a][1];//dp表示第a個(gè)洞穴，消耗i個(gè)士兵獲得的大腦，投入再多的士兵也只能獲得這些大腦for (int i = 0; i < roomsList[a].size(); i++) {//找到本節(jié)點(diǎn)所能到的節(jié)點(diǎn)int to = roomsList[a].get(i);if (vis[to] == true) continue;//如果已經(jīng)弄完了，就不用弄了dfs_dp(to);//處理下一個(gè)節(jié)點(diǎn)，到最后一次，dp中temp之后都存放了能獲得的大腦數(shù)for (int j = m; j >= temp; j--) {//j表示從temp到m所在的列數(shù)，重新修改a節(jié)點(diǎn)消耗temp個(gè)士兵所獲得的大腦數(shù)，加上了子節(jié)點(diǎn)for (int k = 1; k <= j - temp; k++)//dp[a][j] = Math.max(dp[a][j], dp[a][j - k] + dp[to][k]);//da[a][j-k]從第1列到temp列，表示還沒有被修改}}}static List<Hdu1011DataStructure> read() {Scanner scanner = new Scanner(System.in);String nm[] = scanner.nextLine().split(" ");List<Hdu1011DataStructure> hdu1011DataStructureList = new ArrayList<>();while (!nm[0].equals("-1")) {int n = Integer.parseInt(nm[0]);Hdu1011DataStructure h1011DataStructure = new Hdu1011DataStructure();h1011DataStructure.setN(n);h1011DataStructure.setM(Integer.parseInt(nm[1]));//存放蟲子數(shù)量和大腦數(shù)量n行int bugs_brains[][] = new int[n + 1][2];for (int i = 1; i < n + 1; ++i) {String bug_brain[] = scanner.nextLine().split(" ");bugs_brains[i][0] = Integer.parseInt(bug_brain[0]);bugs_brains[i][1] = Integer.parseInt(bug_brain[1]);}h1011DataStructure.setBugs_brains(bugs_brains);//得到本次的大腦和蟲子//存放房間的情況n-1行roomsList = new ArrayList[n + 1];//計(jì)數(shù)從1開始for (int i = 0; i < roomsList.length; i++) {//初始化roomsList[i] = new ArrayList<Integer>();}for (int i = 0; i < n - 1; i++) {String room[] = scanner.nextLine().split(" ");int a = Integer.parseInt(room[0]);int b = Integer.parseInt(room[1]);roomsList[a].add(b);roomsList[b].add(a);}h1011DataStructure.setRooms(roomsList);//得到本次的房間關(guān)系hdu1011DataStructureList.add(h1011DataStructure);nm = scanner.nextLine().split(" ");}return hdu1011DataStructureList;} }

對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)（Java對(duì)象）：

import java.util.ArrayList; import java.util.Arrays;public class Hdu1011DataStructure {private int n, m;//n表示房間個(gè)數(shù)，m表示士兵數(shù)量private int bugs_brains[][];//i 0表示蟲子數(shù)，i 1表示大腦數(shù)量private ArrayList<Integer> rooms[];//數(shù)組i=1中的列表中的內(nèi)容為1所能到的節(jié)點(diǎn)@Overridepublic String toString() {return "Hdu1011DataStructure{" +"n=" + n +", m=" + m +", bugs_brains=" + Arrays.toString(bugs_brains) +", rooms=" + rooms +'}';}public ArrayList<Integer>[] getRooms() {return rooms;}public void setRooms(ArrayList<Integer>[] rooms) {this.rooms = rooms;}public int getN() {return n;}public void setN(int n) {this.n = n;}public int getM() {return m;}public void setM(int m) {this.m = m;}public int[][] getBugs_brains() {return bugs_brains;}public void setBugs_brains(int[][] bugs_brains) {this.bugs_brains = bugs_brains;} }

?

總結(jié)

以上是生活随笔為你收集整理的Hdu1011：星舰部队（java实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。