火车运输问题描述钢厂有一辆用于运送废旧钢材的火车它具有两节车厢其中车厢 11 的最大载重量为 AA车厢 22 的最大载重量为 BB。现在一共有 NN 件废旧钢材需要被运输其中第 ii 件钢材的重量为 wiwi。为了最大化运输效率车长想要一次性运输走重量尽可能多的钢材请你帮助车长计算出一次运输最多可以带走多大重量的钢材。每件钢材都是独立的不可分割的只能被放置在某一节车厢中。在装载钢材时只需要考虑重量条件即可。输入格式输入的第一行包含三个整数 NNAABB用一个空格分隔分别表示钢材的数目以及两节车厢的最大载重。第二行包含 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≤2001≤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 N1010,mod(int)1e97; 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 bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int AInteger.parseInt(st.nextToken()),BInteger.parseInt(st.nextToken()); stnew 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[iw][j]就存在 //如果说f[i][j]状态存在 如果将当前货物放到第二个背包中不会超过最大容量 则f[i][jw]就存在 f[0][0]true; for (int w 1; w n; w) { backnew boolean[N][N];//这里要新开数组 不新开的话 fback 会直接将这两个指向同一个数组 //相等于原地修改 for (int k 0; k A; k) { back[k]Arrays.copyOfRange(f[k], 0, B1); } for (int i 0; i A; i) { for (int j 0; j B; j) { if(!f[i][j])continue; if(ia[w]A){ back[ia[w]][j]true; } if(ja[w]B){ back[i][ja[w]]true; } } } fback; } int resInteger.MIN_VALUE; for (int i 0; i A; i) { for (int j 0; j B; j) { if(f[i][j]){ resMath.max(res, ij); } } } 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≤b1b2...bm≤n1≤b1b2...bm≤n。ab1ab2...abmab1ab2...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 N5*1010,mod(int)1e97; 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 bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } if(n1){ bw.write(1); bw.flush(); return; } int ans1; //如果原数组不修改 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); } ansMath.max(ans, pre[i]); } //可以划分为修改开头修改结尾修改中间 //1.修改开头 //若修改某一个位置的数使其成为该子序列的开头 使得找到的序列尽可能的长 也就是说将这个位置改成零(最小的数) //当我们修改这个位置的数为零的时候我们需要知道这个位置往后的所有位置中,以所有位置的数字开头的最长子序列的长度是多少 //但有一个前提是这个开头必须大于零 以至于零可以接在前面 //我们找到那个最长子序的长度加一就是修改这个位置所对应的最大值 suffi[n]1; for (int i n-1; i 0; i--) { suffi[i]1; for (int j i1; j n; j) { if(a[i]a[j])suffi[i]Math.max(suffi[i], suffi[j]1); } } int maxsuffi[]new int[n2]; int maxz1; for (int i n; i 0; i--) { maxzMath.max(maxz, suffi[i]); maxsuffi[i]maxz; } int nonzerosuffi[]new int[n2];//记录以该位置为开头的序列中开头那个数大于零的最大长度 类似于筛选 for (int i 1; i n; i) { if(a[i]0){ nonzerosuffi[i]maxsuffi[i]; } } for (int i 1; i n; i) { ansMath.max(ans, nonzerosuffi[i1]1); } //2.修改结尾 只需要找到最大长度然后在末尾加上一个最大的数就可以。 int maxpre[]new int[n2]; int maz11; for (int i 1; i n; i) { maxpre[i]Math.max(maz1,pre[i]); } for (int i 2; i n; i) {//不可修改第一个 ansMath.max(ans, maxpre[i-1]1); } //3.修改中间某个位置的数 for (int i 1; i n; i) { for (int j i2; j n; j) {//至少中间有一个数 if(a[i]1a[j]){//如果说两个数之间不是相邻的也就是说不是像2 3 ,5 6 而是像1 3,5 9 ,才有可能插进去一个数 ansMath.max(ans, pre[i]1suffi[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 N5*1010,mod(int)1e97; 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 bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { // StringTokenizer stnew StringTokenizer(br.readLine()); // nInteger.parseInt(st.nextToken()); // stnew 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的时候取到最大值 SetLong possiblescorenew HashSet();//存储所有能达到的和 possiblescore.add(0L);//加L long s0; for(int num:nums){ //每遍历到一个数 在我所有能到达的和的之上再加上这个数 //一般不边遍历边修改 可以先加入的新的集合 随后合并 SetLong tsetnew HashSet(); for (long sum:possiblescore) { tset.add(sumnum); } possiblescore.addAll(tset); snum; } long targets/2; long diffLong.MAX_VALUE; long bestx0; for (long possible:possiblescore) { if(Math.abs(possible-target)diff){ bestxpossible; diffMath.abs(possible-target); } } BigInteger bigInteger1BigInteger.valueOf(bestx); BigInteger bigInteger2BigInteger.valueOf(s-bestx); BigInteger resbigInteger1.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≤1040≤B≤1040≤B≤1041≤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 N10010; 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 bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int mInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken());; for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); attack[i]Integer.parseInt(st.nextToken()); cost[i]Integer.parseInt(st.nextToken()); } //因为是共同发起进攻 所以结果只取决于最大的生命值 int maxlifeInteger.MIN_VALUE; for (int i 1; i m; i) { stnew StringTokenizer(br.readLine()); life[i]Integer.parseInt(st.nextToken()); maxlifeMath.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(jcost[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 cou1; while(cou*f[b]maxlife cou1000){ cou1; } if(cou1000)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≤1040≤W≤1030≤W≤103。对于 100100% 的评测数据n≤∑mi≤105n≤∑mi≤1050≤W≤4×1040≤W≤4×1041≤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 N200010; 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 bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int WInteger.parseInt(st.nextToken()); int p1; for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); int vvInteger.parseInt(st.nextToken()); int wwInteger.parseInt(st.nextToken()); int mmInteger.parseInt(st.nextToken()); int k1; while(kmm){ v[p]k*vv; w[p]k*ww; p; k1; } k1; if(mm-k0){ 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(); } }
