題目描述

有一個物品隊列?\frak BB，初始時為空。現在共有三種操作。每個操作會給定三個整數?\mathrm{op},x,yop,x,y，其中?\mathrm{op}op?表示操作種類，x,yx,y?是操作的參數。操作分為如下三種：

• 11：向?\frak BB?尾部添加一個物品，它的體積為?xx，價值為?yy。
• 22：把?\frak BB?尾部最后物品移除。保證此時最少有一個物品。
• 33：有一個體積為?xx?的背包。用?\frak BB?內的物品填充它，每個物品最多用一次，詢問最多能獲得多大的價值。提示：當?\frak BB?為空時，相當于沒有物品可用，答案就是?00。

對于操作?22?和?33，請忽略多余的參數。

本題強制在線。強制在線的方式請見輸入格式。

輸入格式

• 第一行有兩個正整數?n,m_{\max}n,mmax?，表示操作個數以及操作?33?提到的背包的體積的最大值。
• 接下來?nn?行，每行給定三個整數?\mathrm{op},x',y'op,x′,y′。將?x',y'x′,y′?分別異或上?\mathrm{lastans}lastans?得到該次詢問真正的?x,yx,y。其中，\mathrm{lastans}lastans?是上一次操作?33?詢問的結果。在第一次操作?33?前，\mathrm{lastans}=0lastans=0。

輸出格式

• 輸出有若干行，表示每次?33?操作的結果。

輸入輸出樣例

輸入 #1復制

10 10 1 3 4 1 5 5 3 4 1 3 12 5 1 14 3 3 1 8 2 11 11 3 2 11 2 8 8 3 12 8

輸出 #1復制

4 9 10 9 4

說明/提示

樣例解釋

解碼后的輸入數據為：

10 10 1 3 4 1 5 5 3 4 1 3 8 1 1 7 10 3 8 1 2 1 1 3 8 1 2 1 1 3 5 1

對于十次操作，物品序列的情況如下；

• 加入體積為?33，價值為?44?的物品。物品序列為?\{(3,4)\}{(3,4)}。
• 加入體積為?55，價值為?55?的物品。物品序列為?\{(3,4),(5,5)\}{(3,4),(5,5)}。
• 查詢體積為?44?的背包能裝下的物品價值最大值。此時只能裝第一個物品，于是答案為?44。
• 查詢體積為?88?的背包能裝下的物品價值最大值。此時可把兩個物品都裝下，答案為?99。
• 加入體積為?77，價值為?1010?的物品。物品序列為?\{(3,4),(5,5),(7,10)\}{(3,4),(5,5),(7,10)}。
• 查詢體積為?88?的背包能裝下的物品價值最大值。此時直接裝第三個物品獲得的價值大于裝下另外兩個，于是答案為?1010。
• 刪除最后一個物品。此時物品序列為?\{(3,4),(5,5)\}{(3,4),(5,5)}。
• 查詢體積為?88?的背包能裝下的物品價值最大值。此時可把兩個物品都裝下，答案為?99。
• 刪除最后一個物品。此時物品序列為?\{(3,4)\}{(3,4)}。
• 查詢體積為?55?的背包能裝下的物品價值最大值。此時只有一個物品可裝，答案為?44。

數據范圍及約定

對于全部數據，1\le n\le 3\times 10^41≤n≤3×104，1\le m_{\max}\le 2\times 10^41≤mmax?≤2×104，1\le x, y\le 2\times 10^41≤x,y≤2×104。

首先來個內存不通過的代碼：使用暴力dfs

import java.util.*;import java.util.Scanner;public class Main {public static Integer n;public static Integer max;public static Integer x[];public static Integer y[];public static Integer op[];public static Integer zt[];public static Integer num = 0;public static Integer lastans = 0;public static List<Integer> listx = new ArrayList<>();public static List<Integer> listy = new ArrayList<>();public static void main(String[] args) {Scanner sca = new Scanner(System.in);n = sca.nextInt();max = sca.nextInt();x = new Integer[n];y = new Integer[n];op = new Integer[n];zt = new Integer[n];for(int i = 0;i<n;i++) {op[i] = sca.nextInt();x[i] = sca.nextInt();y[i] = sca.nextInt();zt[i] = 0;}// 解碼數據for(int i = 0;i<n;i++) {x[i] = x[i]^lastans;y[i] = y[i]^lastans; // System.out.println(x[i]+" "+y[i]+"");if(op[i]==1) {listx.add(x[i]);listy.add(y[i]);}else if (op[i]==2) {if(listx.size()>1) {listx.remove(listx.size()-1);listy.remove(listy.size()-1);}}else if (op[i]==3) { // 搜尋最大的價值dfs(x[i],0);System.out.println(num);lastans = num;num = 0; // System.out.println(maxs);}// System.out.println(x[i]+","+y[i]+" :"+listx+" "+listy);}} // 剩余當前背包mx 4 當前背包內價值my 第幾個物品的索引index public static int dfs(Integer mx,Integer my) {if(listx.size()==0) {return 0;}for(int i = 0;i<listx.size();i++) {if(zt[i]==0) {//如果這個沒在包內 // System.out.println("zt.get(i)："+zt[i]);if(mx>=listx.get(i)) {//這個包是否能裝下該物品mx = mx-listx.get(i);//剩余容量my = my+listy.get(i);//當前價值if(my>num) {//存儲最大的有效價值num = my;}zt[i]=1; // 進行下一個搜索dfs(mx, my);mx = mx+listx.get(i);//剩余容量my = my-listy.get(i);//當前價值zt[i]=0;}else {zt[i] = 1; // 進行下一個搜索dfs(mx, my);zt[i] = 0;}}}return 0;}}

對代碼進行優化 ,不會了...

?

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;import java.util.*;public class Main {public static List<Integer> listx = new ArrayList<>(),listy = new ArrayList<>();//存放大小 價值public static int dp[][],dp1[],dp2[],m;public static void main(String[] args) throws IOException {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));int lastans = 0;String s = reader.readLine();int n = Integer.parseInt(s.split(" ")[0]);//一共幾行int max = Integer.parseInt(s.split(" ")[1]);//背包體積最大值int ma = 0;dp1 = new int[max+1];dp2 = new int[max+1];for(int i=0;i<n;i++) {String s1 = reader.readLine();int op = Integer.parseInt(s1.split(" ")[0]);//編號類型int x = Integer.parseInt(s1.split(" ")[1]);//空間int y = Integer.parseInt(s1.split(" ")[2]);//價值x = x^lastans;y = y^lastans;if(op==3) {lastans = dp1[x];System.out.println(dp1[x]);}else if(op==1){for(int j = max;j>=x;j--) {dp1[j] = Math.max(dp1[j], dp1[j-x]+y);}}else if(op==2){for(int j = max;j>=x;j--) {dp1[j] = Math.min(dp1[j], dp1[j-x]-y);}}}}}

?

總結

以上是生活随笔為你收集整理的T293037 [传智杯 #5 练习赛] 白色旅人的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。