笔试

String[] input_pre sc.nextLine().split( ); input[i][0] Integer.parseInt(input_pre[0]); input[i][1] Integer.parseInt(input_pre[1]); total input[i][0]; int[] blocks new int[total]; int cur 0; for (int i 0; i N; i ) { for (int j 0; j input[i][0]; j ) { blocks[cur ] input[i][1]; int M Integer.parseInt(sc.nextLine()); String[] need_pre sc.nextLine().split( ); int[] need new int[M]; for (int i 0; i M; i ) { need[i] Integer.parseInt(need_pre[i]); System.out.println(alloc(blocks, need)); static boolean[] used; static int res -1; static int cur_res 0; public static int alloc(int[] blocks, int[] need) { for (int i 0; i blocks.length; i ) { cur_res blocks[i]; used new boolean[blocks.length]; dfs(0, blocks, need); return res; public static void dfs(int index, int[] blocks, int[] need) { if (index need.length) { int sum 0; for (int i 0; i blocks.length; i ) { if (!used[i]) sum blocks[i]; res Math.max(sum, res); return; for (int i 0; i blocks.length; i ) { if (blocks[i] need[index]) { if (!used[i] cur_res - blocks[i] res)//剪枝 continue; boolean cur_state used[i]; if (!cur_state) cur_res - blocks[i];//这个内存块要从结果中去除 blocks[i] - need[index]; used[i] true; dfs(index 1, blocks, need); used[i] cur_state; blocks[i] need[index]; if (!cur_state) cur_res blocks[i]; 第三题

对于两个单调递增整数序列s1, s2, 在其中可能存在这样的子序列 ss1, ss2
对于任意i有(ss1[i 1] – ss1[i]) (ss2[i 1] – ss2[i]) ,
请找出这些子序列中元素个数最多的子序列。
子序列定义 对于长度为N的序列S 从其中删除n个(0 n N)元素后就得到一个子序列SS
输入描述: 两个单调递增整数序列 单个元素取值范围 -10^9 ss[i] 10^9 0 N 10000
输出描述: 如果能找到子序列 则第一行输出子序列长度 第二三行输出子序列。
如果有多个满足条件子序列 输出元素最小子序列。 如果找不到子序列 输出0即可。

 示例1
 1 2 3 4 5
 2 4 6 8
 1 3 5
 2 4 6
 1 2 3 4 5
 2 7 12 17
 说明 无匹配数组

思路

双重循环来枚举两个序列的起点 再用双指针依次向后扫描。
剪枝 用一个二维布尔数组来维护是否被访问过 如果visited[i][j]被访问过了 就不用考虑分别以i和j为起点的两个数组了。

Python解法

arr1 list(map(int, input().strip().split()))
arr2 list(map(int, input().strip().split()))
beginIndex1 0
beginIndex2 0
ss1 []
ss2 []
flag [[True for _ in range(len(arr2))] for _ in range(len(arr1))]
for beginIndex1 in range(len(arr1)):
 for beginIndex2 in range(len(arr2)):
 if not flag[beginIndex1][beginIndex2]:
 continue
 newSS1 [arr1[beginIndex1]]
 newSS2 [arr2[beginIndex2]]
 index1 beginIndex1 1
 index2 beginIndex2 1
 while index1 len(arr1) and index2 len(arr2):
 while index1 len(arr1) and arr1[index1]-arr1[beginIndex1] arr2[index2]-arr2[beginIndex2]:
 index1 1
 if index1 len(arr1):
 break
 if arr1[index1]-arr1[beginIndex1] arr2[index2]-arr2[beginIndex2]:
 newSS1.append(arr1[index1])
 newSS2.append(arr2[index2])
 index1 1
 index2 1
 if index1 len(arr1):
 break
 while index2 len(arr2) and arr1[index1]-arr1[beginIndex1] arr2[index2]-arr2[beginIndex2]:
 index2 1
 if index2 len(arr2):
 break
 if arr1[index1]-arr1[beginIndex1] arr2[index2]-arr2[beginIndex2]:
 newSS1.append(arr1[index1])
 newSS2.append(arr2[index2])
 flag[index1][index2] False
 index1 1
 index2 1
 if len(newSS1) len(ss1):
 ss1 newSS1[:]
 ss2 newSS2[:]
if len(ss1) 1:
 print(0)
else:
 print(len(ss1))
 print( .join(str(i) for i in ss1))
 print( .join(str(i) for i in ss2))

Java解法

import java.util.*;
public class Huawei {
 public static void main(String[] args) {
 Scanner sc new Scanner(System.in);
 String[] arr1_pre sc.nextLine().split( );
 String[] arr2_pre sc.nextLine().split( );
 int[] arr1 new int[arr1_pre.length];
 int[] arr2 new int[arr2_pre.length];
 for (int i 0; i arr1_pre.length; i ) {
 arr1[i] Integer.parseInt(arr1_pre[i]);
 for (int i 0; i arr2_pre.length; i ) {
 arr2[i] Integer.parseInt(arr2_pre[i]);
 List List Integer res LongestCommonSequence(arr1, arr2);
 System.out.println(res);
 public static List List Integer LongestCommonSequence(int[] arr1, int[] arr2) {
 int len1 arr1.length, len2 arr2.length;
 boolean visited[][] new boolean[len1][len2];//用于剪枝
 List Integer res1 new ArrayList ();
 List Integer res2 new ArrayList ();
 for (int i 0; i len1; i ) {
 for (int j 0; j len2; j ) {
 if (visited[i][j])
 continue;
 List Integer temp1 new ArrayList ();
 List Integer temp2 new ArrayList ();
 temp1.add(arr1[i]);
 temp2.add(arr2[j]);
 int ptr1 i 1, ptr2 j 1;
 while (ptr1 len1 ptr2 len2) {
 while (ptr1 len1 arr1[ptr1] - arr1[i] arr2[ptr2] - arr2[j]) {
 ptr1 ;
 if (ptr1 len1)
 break;
 if (arr1[ptr1] - arr1[i] arr2[ptr2] - arr2[j]) {
 temp1.add(arr1[ptr1]);
 temp2.add(arr2[ptr2]);
 ptr1 ;
 ptr2 ;
 if (ptr1 len1)
 break;
 while (ptr2 len2 arr1[ptr1] - arr1[i] arr2[ptr2] - arr2[j]) {
 ptr2 ;
 if (ptr2 len2)
 break;
 if (arr1[ptr1] - arr1[i] arr2[ptr2] - arr2[j]) {
 temp1.add(arr1[ptr1]);
 temp2.add(arr2[ptr2]);
 visited[ptr1][ptr2] true;//剪枝
 ptr1 ;
 ptr2 ;
 if (temp1.size() res1.size()) {
 res1 temp1;
 res2 temp2;
 if (res1.size() 1) {
 return null;
 List List Integer res new ArrayList ();
 res.add(res1);
 res.add(res2);
 return res;