火车运输
问题描述
钢厂有一辆用于运送废旧钢材的火车，它具有两节车厢，其中车厢 11 的最大载重量为 AA，车厢 22 的最大载重量为 BB。现在一共有 NN 件废旧钢材需要被运输，其中第 ii 件钢材的重量为 wiwi。为了最大化运输效率，车长想要一次性运输走重量尽可能多的钢材，请你帮助车长计算出一次运输最多可以带走多大重量的钢材。
每件钢材都是独立的不可分割的，只能被放置在某一节车厢中。在装载钢材时只需要考虑重量条件即可。
输入格式
输入的第一行包含三个整数 NN，AA，BB，用一个空格分隔，分别表示钢材的数目以及两节车厢的最大载重。
第二行包含 NN 个整数，分别表示 w1w1, w2w2, ..., wnwn，相邻两个整数之间使用一个空格分隔。
输出格式
输出一个整数表示答案。
样例输入
3 10 8 8 9 1样例输出
18样例说明
车厢 11 装入第 22 件和第 33 件钢材，车厢 22 装入第 11 件钢材。
评测用例规模与约定
对于 30%30% 的评测用例，1≤N≤101≤N≤10；
对于所有评测用例，1≤N≤2001≤N≤200，1≤wi,A,B≤1,0001≤wi,A,B≤1,000。
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N=1010,mod=(int)1e9+7; static int a[]=new int[N]; static boolean f[][]=new boolean[N][N]; static boolean back[][]; static int n; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int A=Integer.parseInt(st.nextToken()),B=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(st.nextToken()); } //问题是典型的双背包问题 //f[i][j]表示是否存在使得第一个背包的重量是恰好是i，第二个背包的重量恰好是j的方案 //如果说f[i][j]状态存在 如果将当前货物放到第一个背包中，不会超过最大容量 则f[i+w][j]就存在 //如果说f[i][j]状态存在 如果将当前货物放到第二个背包中，不会超过最大容量 则f[i][j+w]就存在 f[0][0]=true; for (int w = 1; w <= n; w++) { back=new boolean[N][N];//这里要新开数组 不新开的话 f=back 会直接将这两个指向同一个数组 //相等于原地修改 for (int k = 0; k <= A; k++) { back[k]=Arrays.copyOfRange(f[k], 0, B+1); } for (int i = 0; i <= A; i++) { for (int j = 0; j <= B; j++) { if(!f[i][j])continue; if(i+a[w]<=A){ back[i+a[w]][j]=true; } if(j+a[w]<=B){ back[i][j+a[w]]=true; } } } f=back; } int res=Integer.MIN_VALUE; for (int i = 0; i <= A; i++) { for (int j = 0; j <= B; j++) { if(f[i][j]){ res=Math.max(res, i+j); } } } bw.write(res+""); br.close(); bw.flush(); bw.close(); } }简单的LIS问题【算法赛】
问题描述
最长上升子序列（Longest Increasing Subsequence），简称 LIS，指的是一个序列中最长的一个子序列，满足其单调递增。
例如，对于一个序列 a1,a2,a3,a4,...,ai,...,ana1,a2,a3,a4,...,ai,...,an，存在一个序列 b1,b2,...,bmb1,b2,...,bm，满足：
- 1≤b1<b2<...<bm≤n1≤b1<b2<...<bm≤n。
- ab1<ab2<...<abmab1<ab2<...<abm。
那么我们称 {ab1,ab2,...,abm}{ab1,ab2,...,abm} 为 {ai}{ai} 的一个上升子序列。
最长的上升子序列就是最长（元素数量最多）的一个上升子序列。
小蓝学到了这个知识点，并且学会一些用来计算 LIS 的常见算法。
于是小蓝向邻居小桥炫耀他学到的新知识，但是小桥显然不会让小蓝如此得意，于是他提出了一个新的问题：
给定一个长度为 nn 的序列 {ai}{ai}，小蓝可以选择其中的一个位置，修改为 0∼101000∼10100 中的任何一个整数。具体来说，小蓝可以选择一个位置 p(p∈[1,n])p(p∈[1,n])，将 apap 重新赋值为 0∼101000∼10100 中的任意一个整数。请问修改过后，最长上升子序列的长度是多少？
小蓝看到这个问题，两眼一抹黑，于是请你帮他解决这个问题。
输入格式
第一行输入一个整数 nn。
第二行输入 nn 个整数 a1,a2,...,ai,...,ana1,a2,...,ai,...,an，用来表示序列 aa 的每个值。
输出格式
输出一个整数，表示修改后的最长上升子序列长度。
样例输入
5 2 5 4 3 7样例输出
4说明
修改 33 为 55，得到 2,5,4,5,72,5,4,5,7，得到最长上升子序列为 2,4,5,72,4,5,7。
评测数据范围
1≤n≤5×103,0≤ai≤1091≤n≤5×103,0≤ai≤109。
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N=5*1010,mod=(int)1e9+7; static int a[]=new int[N]; static int pre[]=new int[N];//pre[i]表示以当前数为结尾的最长上升子序列的长度 static int suffi[]=new int[N]; //suffi[i]表示以当前数为开头的最长上升子序列的长度 static int n; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(st.nextToken()); } if(n==1){ bw.write(1+""); bw.flush(); return; } int ans=1; //如果原数组不修改 for (int i = 1; i <= n; i++) { pre[i]=1; for (int j = 1; j < i; j++) { if(a[j]<a[i])pre[i]=Math.max(pre[i], pre[j]+1); } ans=Math.max(ans, pre[i]); } //可以划分为修改开头，修改结尾，修改中间 //1.修改开头 //若修改某一个位置的数，使其成为该子序列的开头 使得找到的序列尽可能的长 也就是说将这个位置改成零(最小的数) //当我们修改这个位置的数为零的时候，我们需要知道这个位置往后的所有位置中,以所有位置的数字开头的最长子序列的长度是多少 //但有一个前提是这个开头必须大于零 以至于零可以接在前面 //我们找到那个最长子序的长度加一就是修改这个位置所对应的最大值 suffi[n]=1; for (int i =n-1; i > 0; i--) { suffi[i]=1; for (int j = i+1; j <= n; j++) { if(a[i]<a[j])suffi[i]=Math.max(suffi[i], suffi[j]+1); } } int maxsuffi[]=new int[n+2]; int maxz=1; for (int i = n; i > 0; i--) { maxz=Math.max(maxz, suffi[i]); maxsuffi[i]=maxz; } int nonzerosuffi[]=new int[n+2];//记录以该位置为开头的序列中，开头那个数大于零的最大长度 类似于筛选 for (int i = 1; i <= n; i++) { if(a[i]>0){ nonzerosuffi[i]=maxsuffi[i]; } } for (int i = 1; i < n; i++) { ans=Math.max(ans, nonzerosuffi[i+1]+1); } //2.修改结尾 只需要找到最大长度然后在末尾加上一个最大的数就可以。 int maxpre[]=new int[n+2]; int maz1=1; for (int i = 1; i < n; i++) { maxpre[i]=Math.max(maz1,pre[i]); } for (int i = 2; i <= n; i++) {//不可修改第一个 ans=Math.max(ans, maxpre[i-1]+1); } //3.修改中间某个位置的数 for (int i = 1; i <= n; i++) { for (int j = i+2; j <= n; j++) {//至少中间有一个数 if(a[i]+1<a[j]){//如果说两个数之间不是相邻的，也就是说不是像2 3 ,5 6 而是像1 3,5 9 ,才有可能插进去一个数 ans=Math.max(ans, pre[i]+1+suffi[j]); } } } bw.write(ans+""); br.close(); bw.flush(); bw.close(); } }划分
问题描述
给定 4040 个数，请将其任意划分成两组，每组至少一个元素。每组的权值为组内所有元素的和。划分的权值为两组权值的乘积。请问对于以下 4040 个数，划分的权值最大为多少。
5160 9191 6410 4657 7492 1531 8854 1253 4520 9231 1266 4801 3484 4323 5070 1789 2744 5959 9426 4433 4404 5291 2470 8533 7608 2935 8922 5273 8364 8819 7374 8077 5336 8495 5602 6553 3548 5267 9150 3309在试题包中有一个名为 \verb|nums.txt| 的文本文件，文件中的数与题面上的数相同。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.math.BigInteger; import java.util.*; public class Main { static int N=5*1010,mod=(int)1e9+7; static int a[]=new int[N]; static int pre[]=new int[N];//pre[i]表示以当前数为结尾的最长上升子序列的长度 static int suffi[]=new int[N]; //suffi[i]表示以当前数为开头的最长上升子序列的长度 static int n; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { // StringTokenizer st=new StringTokenizer(br.readLine()); // n=Integer.parseInt(st.nextToken()); // st=new StringTokenizer(br.readLine()); // for (int i = 1; i <= n; i++) { // a[i]=Integer.parseInt(st.nextToken()); // } int[] nums = { 5160, 9191, 6410, 4657, 7492, 1531, 8854, 1253, 4520, 9231, 1266, 4801, 3484, 4323, 5070, 1789, 2744, 5959, 9426, 4433, 4404, 5291, 2470, 8533, 7608, 2935, 8922, 5273, 8364, 8819, 7374, 8077, 5336, 8495, 5602, 6553, 3548, 5267, 9150, 3309 }; //一部分的和是x 另一部分的和是s-x s为所有数的总和 //最终答案是x*(s-x) //可以知道 在x/2的时候取到最大值 Set<Long> possiblescore=new HashSet<>();//存储所有能达到的和 possiblescore.add(0L);//加L long s=0; for(int num:nums){ //每遍历到一个数 在我所有能到达的和的之上，再加上这个数 //一般不边遍历边修改 可以先加入的新的集合 随后合并 Set<Long> tset=new HashSet<>(); for (long sum:possiblescore) { tset.add(sum+num); } possiblescore.addAll(tset); s+=num; } long target=s/2; long diff=Long.MAX_VALUE; long bestx=0; for (long possible:possiblescore) { if(Math.abs(possible-target)<diff){ bestx=possible; diff=Math.abs(possible-target); } } BigInteger bigInteger1=BigInteger.valueOf(bestx); BigInteger bigInteger2=BigInteger.valueOf(s-bestx); BigInteger res=bigInteger1.multiply(bigInteger2); bw.write(res.toString()); br.close(); bw.flush(); bw.close(); } }明日方舟大作战！
问题描述
《明日方舟》是由鹰角网络所开发的一款策略塔防手机游戏。在每次的作战行动中，作为博士的你在战斗开始前需要合理分配干员进行战斗，以达到最高的战斗效率。
现有 nn 个干员，每个干员有攻击力和费用两个属性。同时有 mm 个敌人，每个敌人具有一定的生命值。你的任务是选择一些干员进行战斗，使得总费用不超过给定的预算 BB，同时击败所有敌人。
干员与敌人的关系如下：
- 若选择干员 ii 进行战斗，则其可以在每一回合内对所有敌人造成 attackiattacki 的伤害。
- 若敌人 jj 的生命值降为 00 及以下，则该敌人被击败。
- 敌人不会行动，不会发起攻击。
请你选择合适的干员，计算最小回合数以击败所有敌人。
输入格式
第一行包含三个整数 nn、mm 和 BB，表示干员数量、敌人数量和总预算（1≤n,m,B≤1041≤n,m,B≤104）。
接下来 nn 行，每行包括两个整数 attackiattacki 和 costicosti ，表示第 ii 个干员的攻击力和费用（1≤attacki,costi≤1041≤attacki,costi≤104）。
接下来 mm 行，每行包括一个整数 lifejlifej ，表示第 jj 个敌人的生命值（1≤lifej≤1041≤lifej≤104）。
输出格式
输出一个整数，表示击败所有敌人所需的最小的回合数。若无法在预算内击败所有敌人，则输出 −1−1 。
样例输入
3 2 10 5 4 3 3 2 2 6 5样例输出
1测评数据规模
1≤n,m≤1041≤n,m≤104，0≤B≤1040≤B≤104，1≤attacki,costi,lifej≤1041≤attacki,costi,lifej≤104。
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.math.BigInteger; import java.util.*; public class Main { static int N=10010; static int attack[]=new int[N]; static int cost[]=new int[N]; static int life[]=new int[N]; static int f[]=new int[N]; static int n; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int m=Integer.parseInt(st.nextToken()),b=Integer.parseInt(st.nextToken());; for (int i = 1; i <= n; i++) { st=new StringTokenizer(br.readLine()); attack[i]=Integer.parseInt(st.nextToken()); cost[i]=Integer.parseInt(st.nextToken()); } //因为是共同发起进攻 所以结果只取决于最大的生命值 int maxlife=Integer.MIN_VALUE; for (int i = 1; i <= m; i++) { st=new StringTokenizer(br.readLine()); life[i]=Integer.parseInt(st.nextToken()); maxlife=Math.max(life[i], maxlife); } //所以我们只需要求在不超过预算的情况之下看它的最大攻击值能累加到多少 //这就相当于是0/1背包问题 //f[i][j]定义为 只考虑前i个干员 最大预算为j的最大的累加攻击值 for (int i = 1; i <= n; i++) { for (int j = b; j > 0 ; j--) { if(j>=cost[i]){ f[j]=Math.max(f[j], f[j-cost[i]]+attack[i]); } } } if(f[b]>=maxlife){ bw.write(String.valueOf(1)); bw.flush(); return; }else{ int cou=1; while(cou*f[b]<maxlife && cou<=1000){ cou+=1; } if(cou<=1000)bw.write(cou+""); else bw.write("-1"); bw.flush(); return; } } }冒险岛的魔法果实
问题描述
在冒险岛的深处，小萌探索到了一个传说中的魔法果实园。这里满是各种神奇的魔法果实，吃了可以增加不同的魔法能量。
小萌想带一些魔法果实回去，但是他的背包空间有限。看着这些琳琅满目的魔法果实，小萌很是纠结，决定选择一些最有价值的果实带回去。
小萌对果园里的魔法果实进行了整理，他发现每种果实都有一颗或者多颗。他估算了下每种魔法果实能增加的魔法能量，然后开始了筛选工作：小萌有一个最大容量为 WW 的背包，果园里总共有 nn 种魔法果实，每种果实能增加的魔法能量为 vivi，重量为 wiwi，每种魔法果实有 mimi 颗。小萌希望在背包不超重的前提下，选择一些魔法果实装进背包，使得他们能增加的魔法能量最大。
输入格式
第一行为一个整数 nn 和 WW，分别表示魔法果实种数和背包的最大容量。
接下来 nn 行每行三个整数 vi,wi,mivi,wi,mi，分别表示每种果实能增加的魔法能量，重量，每种魔法果实颗数。
输出格式
输出仅一个整数，表示在背包不超重的情况下收集的魔法果实能增加的最大魔法能量。
样例输入
2 4 2 3 2 1 2 3样例输出
2说明
样例中，最优方案是：
第一种魔法果实 11 个，能量 22。第二种魔法果实 00 个，能量 00。最大能量为 22。
或者，第一种魔法果实 00 个，能量 00。第二种魔法果实 22 个，能量 22。最大能量为 22。
因此，最大魔法能量为 22。
评测数据规模
对于 5050% 的评测数据，n≤∑mi≤104n≤∑mi≤104，0≤W≤1030≤W≤103。
对于 100100% 的评测数据，n≤∑mi≤105n≤∑mi≤105，0≤W≤4×1040≤W≤4×104，1≤n≤1001≤n≤100。
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N=200010; static int v[]=new int[N]; static int w[]=new int[N]; static int f[]=new int[N]; static int n; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int W=Integer.parseInt(st.nextToken()); int p=1; for (int i = 1; i <= n; i++) { st=new StringTokenizer(br.readLine()); int vv=Integer.parseInt(st.nextToken()); int ww=Integer.parseInt(st.nextToken()); int mm=Integer.parseInt(st.nextToken()); int k=1; while(k<=mm){ v[p]=k*vv; w[p]=k*ww; p++; k<<=1; } k>>=1; if(mm-k>0){ v[p]=(mm-k)*vv; w[p]=(mm-k)*ww; p++; } } //相当于是0/1背包 for (int i = 1; i < p; i++) { for (int j = W; j > 0; j--) { if(j-w[i]>=0)f[j]=Math.max(f[j],f[j-w[i]]+v[i]); } } bw.write(f[W]+""); br.close(); bw.flush(); bw.close(); } }
第四章——内部类)
