若干算子构成一个有向无环图，若算子A依赖算子B的输出，则仅当算子B执行完成后才能执行A，没有依赖关系的算子可以并行执行。
已知每个算子的执行时间，求整个网络运行所需要的最小时间。
输入描述：
一共N+1行，第一行输入N，即算子总数
第二到第N+1行包括
算子名称 算子消耗时间 后继算子1 后继算子2 … 后继算子k
（可能存在没有后继算子的算子）
N = int(input()) #数据的大小
res = [0] * N #res[i]表示完成第i个任务所需要的最短时间
for i in range(N):
#处理输入，直接略过第一行数据
_input = list(map(int,input().split()[1:]))
if len(_input) < 2: #如果没有
res[i] += _input[0]
else:
for j in _input[1:]:
res[j] = max(res[j],res[i] + _input[0])
print(max(res))
解法2
有向无环图求一个拓扑排序
N=int(input())
degree={}
matrix={}
op_time={}
father={}
finish_time=[0]*N
for op_idx in range(N):
matrix[op_idx]=[]
degree[op_idx]=0
father[op_idx]=[]
for op_idx in range(N):
op=input().split()
op_time[op_idx]=int(op[1])
for next_op in op[2:]:
next_op=int(next_op)
degree[next_op]+=1
matrix[op_idx].append(next_op)
father[next_op].append(op_idx)
queue=[]
for op_idx in range(N):
if degree[op_idx]==0:
queue.append(op_idx)
tuopu=[]
while len(queue):
cur_node=queue.pop(0)
tuopu.append(cur_node)
for next_node in matrix[cur_node]:
degree[next_node]-=1
if degree[next_node]==0:
queue.append(next_node)
for op_idx in tuopu:
max_time=0
for pre_op in father[op_idx]:
if finish_time[pre_op]>max_time:
max_time=finish_time[pre_op]
finish_time[op_idx]=max_time+op_time[op_idx]
print(max(finish_time))
Java处理输入部分
public class Huawei {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.nextLine());
List> input = new ArrayList<>();
for (int i = 0; i < N; i++) {
String[] nums = sc.nextLine().split(" ");
List suanzi = new ArrayList<>();
suanzi.add(Integer.parseInt(nums[1]));
for (int j = 2; j < nums.length; j++) {
suanzi.add(Integer.parseInt(nums[j]));
}
input.add(suanzi);
}
}
}
第二题
有若干内存块，每个内存块有不同的规格，对内存进行分配，
求剩余完全没有被分配的内存块总大小的最大值。
输入描述：
第一行N，代表内存块的种类。
接下来的N行每一行有两个数字分别是该种内存的数量和内存大小。
第N+2行是M，代表请求的数量。
第N+3行有M个数字，代表每次请求的内存大小。
举例：
输入：
3
2 4
3 8
4 16
4
7 9 11 4
输出：
64
代表有3种内存，容量为4的内存有2个，容量为8的有3个，容量为16的有4个。
接下来4次请求，分别请求7、9、11、4的内存。
第一次分配容量为16的内存。
第二次分配第一次分配后的剩余内存。
第三次分配容量为16的内存。
第四次分配第三次分配后的剩余内存。
此时剩余大小2*4+3*8+2*16=64的内存块完全没有被分配。
用回溯+剪枝的方法来寻找最优解。
剪枝：如果此时的策略已经不如现存的最好策略就直接跳过
class Solution(object):
def __init__(self, blocks, nums):
self.blocks = blocks
self.ans = -1 # 最终的结果
self.use = [False] * len(blocks) # 标记每个内存块的使用状态(True 表示已被使用， False表示未使用)
self.nums = nums
self.nums_len = len(nums)
self.cur_ans = sum(self.blocks) # 表示当前结果，目的是为了剪枝
def dfs(self, idx):
if idx == self.nums_len:
ans = 0
for i in range(len(self.blocks)):
if not self.use[i]:
ans += self.blocks[i]
self.ans = max(self.ans, ans)
return
for i in range(len(self.blocks)):
if self.blocks[i] >= self.nums[idx]:
if not self.use[i] and self.cur_ans - self.blocks[i] <= self.ans:
continue
pre_state = self.use[i]
if not pre_state:
self.cur_ans -= self.blocks[i]
self.blocks[i] -= self.nums[idx]
self.use[i] = True
self.dfs(idx + 1)
self.use[i] = pre_state
self.blocks[i] += self.nums[idx]
if not pre_state:
self.cur_ans += self.blocks[i]
def solve(self):
self.dfs(0)
if self.ans % 1 == 0:
print(int(self.ans))
else:
print(self.ans)
N = int(input())
blocks = []
for i in range(N):
num, block = [int(x) for x in input().split()]
for j in range(int(num)):
blocks.append(block)
M = int(input())
nums = [int(x) for x in input().split()]
print(blocks)
print(nums)
s = Solution(blocks, nums)
s.solve()
Java解法
import java.util.*;
public class Huawei {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.nextLine());
int[][] input = new int[N][2];
int total = 0;
for (int i = 0; i < N; i++) {
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
输出
3
1 3 5
2 4 6
示例2
输入
1 2 3 4 5
2 7 12 17
输出
0
说明 无匹配数组
思路
双重循环来枚举两个序列的起点，再用双指针依次向后扫描。
剪枝：用一个二维布尔数组来维护是否被访问过，如果visited[i][j]被访问过了，就不用考虑分别以i和j为起点的两个数组了。
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 index1arr2[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> res = LongestCommonSequence(arr1, arr2);
System.out.println(res);
}
public static List> LongestCommonSequence(int[] arr1, int[] arr2) {
int len1 = arr1.length, len2 = arr2.length;
boolean visited[][] = new boolean[len1][len2];//用于剪枝
List res1 = new ArrayList<>();
List res2 = new ArrayList<>();
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
if (visited[i][j])
continue;
List temp1 = new ArrayList<>();
List 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> res = new ArrayList<>();
res.add(res1);
res.add(res2);
return res;
}
}
