等我写完快排实验我才发现实验1是二分搜索不是快速排序tnnd都写完了舍不得删
敢于斗争，不怕牺牲 0-快速排序-递归 分析论
1.宏观视角：递归算法，每次将[l,r]区间进行快速排序，并向下递归
2.算法思想
A.极限划分返回：只有一个元素(或溢出)的时候返回
B.中间参考值划分：
中间参考值x，s1 s2左右指针，不断向中间位置靠拢
把大的丢右边去，小的丢左边去
如果s1，s2还没有交叠时候跳出
C.debug注意事项：边界问题
类似于二分搜索算法，受制于int向下取整的特性，l+r>>1可能会损失精度
对于除以2应当分为两种情况【向下取整 l+r>>1】【向上取整 l+r+1>>1】
这会影响到 向下递归时 子区间的划分
最终跳出while时候，s1到mid右侧，s2到mid左侧；此时要思考mid踩在哪个s上
这个我也不知道怎么说，看大家自己的悟性，我是这么理解的
这是我在整数二分搜索中参悟的思想
代码区#include0-快速排序-非递归 分析论#include #include using namespace std; const int N = 1e5 + 7; int node[N], n; void asd(int a[], int l, int r) { if (l >= r) return; int x = a[l + r >> 1], s1 = l - 1, s2 = r + 1; while (s1 < s2) { while (a[++s1] < x) ; //左侧靠近 while (a[--s2] > x) ; //右侧靠近 if (s1 < s2) swap(a[s1], a[s2]); //没有溢出 } // printf("%d %d n", s1, s2); asd(a, l, s2), asd(a, s2 + 1, r); } //如果是从大到小排序，只要改一下两个while中的符号就可以了 //不要去调整s1，s2 //思想上和二分查找是一脉相承的 int main() { //输入 scanf("%d", &n); for (int x = 0; x < n; x++) scanf("%d", &node[x]); //排序 asd(node, 0, n - 1); //输出 for (int x = 0; x < n; x++) printf("%d ", node[x]); return 0; }
使用queue临时存一下l和r，先进去的一定是【大区间】，向下递归的【小区间】存后边
网上找代码真是太难受了，写的又复杂又不直观，学习思想后自己写更舒服
queue是从宏观到微观，宏观工作完成了才会向下递归（弹出queue）
不能使用stack，因为他会在【没有完成工作】的情况下探底
#include1-二分搜索-非递归 分析论#include #include #include #include using namespace std; const int N = 1e5 + 7; int b[N], n; void qsort(int *a, int l, int r) { queue q; //用于存放等待排序的左右指针 //首发入阵 q.push(l), q.push(r); //先做一次左右排序，然后转入queue while (q.size()) //非空的时候，依次弹出 { l = q.front(), q.pop(); r = q.front(), q.pop(); if (l >= r) continue; int s1, s2, x; s1 = l - 1, s2 = r + 1; x = a[l + r >> 1]; //取得中间数值 while (s1 < s2) { // printf("%d %dn", s1, s2); while (a[++s1] < x) ; while (a[--s2] > x) ; if (s1 < s2) swap(a[s1], a[s2]); } q.push(l), q.push(s2), q.push(s2 + 1), q.push(r); } } void show(int *a) { // puts("233"); for (int i = 0; i < n; i++) printf("%d ", a[i]); } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &b[i]); qsort(b, 0, n - 1); show(b); return 0; }
思想过程：【追寻左端点】
1.宏观lr步数，查询t输入
2.while，lr没有交叠
A.mid=l+r>>1（暂定）
思想论：从不满足性质的一侧开始找，部署【首个满足条件元素具有的性质】
（左侧开始找，递增，找首个>=）
应该说左侧都是小的数字，右侧都是大的数字
B.关于 a[mid]的判断
a.首个满足性质的部署mid
思想论：mid满足性质，说明落在了右区间，我们要寻找的左端点应该在左区间找
向下取整时：左区间[l,mid] 右区间[mid+1,r]
向上取整时：左区间[l,mid-1] 右区间[mid,r]
跳出循环时候交叠，r在左侧，l在右侧
b.思考1：r=mid（mid在右区间，我们要去左区间找，所以更新【左区间的右端点r】）
c.反推1：l=mid+1
d.反推2：l+r>>1
思想论：mid踩在左侧r说明向下取整不用+1，mid踩在右侧l说明向上取整需要+1
这里S2就是R，S1就是L，跳出while时候说明左右指针交叠了
结束的时候看一下a[l]，不相等说明这玩意压根就不存在
我们的追踪方法会让l停留在【首个满足该性质的元素】位置上
思想过程：【追寻右端点】
1.宏观lr步数，查询t输入
2.while，lr没有交叠
A.mid=l+r>>1（暂定）
思想论：从不满足性质的一侧开始找，部署【首个满足条件元素具有的性质】
（左侧开始找，递增，找首个>=） 应该说左侧都是小的数字，右侧都是大的数字
B.关于 a[mid]的判断
a.首个满足性质的部署mid
思想论：mid满足性质，说明落在了左区间，我们要寻找的右端点应该在右区间找
向下取整时：左区间[l,mid] 右区间[mid+1,r]
向上取整时：左区间[l,mid-1] 右区间[mid,r]
跳出循环时候交叠，r在左侧，l在右侧
b.思考1：l=mid（mid在左区间，我们要去右区间找，所以更新【右区间的左端点l】）
c.反推1：r=mid-1
d.反推2：l+r+1>>1
思想论：mid踩在右侧l说明向上取整，需要+1
#include1-二分搜索-递归 分析论#include #include using namespace std; const int N = 1e5 + 7; int n, m, a[N]; //《模板示例》 //更新边界R在左侧，L在右侧 //[l,mid]-->r=mid (左侧) l=mid+1 //[mid,r]-->l=mid (右侧) r=mid-1 bool check(int a) { //满足性质的mid处在【左右】哪个区间 return true; } int T1(int l, int r) { while (l < r) { int mid = l + r >> 1; //无需+1型，mid在R位置 if (check(a[mid])) //此时满足的mid在右边区间，答案在左区间，更新R（左区间的右端点） r = mid; else l = mid + 1; } return l; } int T2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; //无需+1型，mid在R位置 if (check(a[mid])) //此时满足的mid在左边区间，答案在右区间，更新L（右区间的左端点） l = mid; else r = mid - 1; } return l; } int main() { scanf("%d%d", &n, &m); for (int x = 0; x < n; x++) scanf("%d", &a[x]); int t; while (m--) { scanf("%d", &t); int l = 0, r = n - 1; while (l < r) //寻找左侧出发点 { int mid = l + r >> 1; if (a[mid] >= t) r = mid; else l = mid + 1; } if (a[l] != t) //首次搜索都搜不到说明根本没有 { printf("-1 -1n"); continue; } printf("%d ", l); //否则，得出起始位置 l = 0, r = n - 1; //寻找右侧终止点 while (l < r) { int mid = l + r + 1 >> 1; if (a[mid] <= t) l = mid; else r = mid - 1; } printf("%dn", r); } return 0; }
稍微改造一下就可以了，思路和上边是一样的，只是while控制改成边缘返回条件罢了
同样通过了ACWING的测试
#include2-最大子段和-暴力 分析论 带了个前缀和 代码区#include #include using namespace std; const int N = 1e5 + 7; int n, m, a[N], t; int getL(int t, int l, int r) { if (l >= r) return l; int mid = l + r >> 1; if (a[mid] >= t) getL(t, l, mid); else getL(t, mid + 1, r); } int getR(int t, int l, int r) { if (l >= r) return r; int mid = l + r + 1 >> 1; if (a[mid] <= t) getR(t, mid, r); else getR(t, l, mid - 1); } int main() { scanf("%d%d", &n, &m); for (int x = 0; x < n; x++) scanf("%d", &a[x]); while (m--) { scanf("%d", &t); int l = getL(t, 0, n - 1); if (a[l] != t) { printf("-1 -1n"); continue; } int r = getR(t, 0, n - 1); printf("%d %dn", l, r); } return 0; }
#include2-最大子段和-递归 分析论#include #include using namespace std; #define LL long long const int N = 1e5 + 7; int n, a[N]; LL maxx=-2e9, b[N]; //堆栈外区不用初始化默认就是0，并且可以开更大的数组 // main里面数组不能太大，并且 void t1() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int e = 0; e < n; e++) for (int s = 0; s <= e; s++) { LL sum = 0; for (int i = s; i <= e; i++) sum += a[i]; maxx = max(maxx, sum); } printf("%lld", maxx); } void t2() { scanf("%d", &n); for (int i = 1; i <= n; i++) //前缀和从1开始存 scanf("%d", &a[i]), b[i] = b[i - 1] + a[i]; for (int e = 1; e <= n; e++) for (int s = 1; s <= e; s++) maxx = max(maxx, b[e] - b[s - 1]); printf("%lld", maxx); } int main() { // t1(); //纯暴力 t2(); //前缀和优化 return 0; }
(1)算法思想
A.部署find(k)函数，用于寻找到【必定选中第k个元素的最大子段和】
部署备忘录m[k]，来记录find(k)的数值，如果递归过程发现find(k)执行过一次了，就从备忘录里面调动（直接return m[k]）（int型函数提前return就算终止掉了不会再往下运行）
B.递归边界：k=0时候，说明递归探底（因为我们数据从a[0]开始存储）
这时候返回a[0]，同时部署m[0]
C.递归划分：思想论·当前选中第k个元素的最佳状态是和之前形成的最大字段和有关的，考虑两种状态
a.选择前面的最大子段和，并且把k号元素加上（衔接过程）
b.不选择前面的最大子段和，重新从当前第k号元素开始（另立门户）
b选项的递归决定了起点的选择，a选项则决定了子段和的长度在哪里
前面最大子段和：find(k-1)
当前k号元素：a[k]
那么我们m[k]=find(k)=max(a[k],a[k]+find[k-1]);
阶段结束后要存储到m[k]中并return
D.最后扫描一遍备忘录m，把max弄出来
E.关于先进书写的补充：return a=b;会先赋值后返回
相当于把【内部语句】拆分到上一行，执行完成后再return
F.关于时间复杂度：这是带着备忘录的递归，只会从n探底到0 1次，其他时间会通过备忘录调取，不会再执行find函数
#include2-最大子段和-分治 分析论#include #include using namespace std; const int N = 1e5 + 7; int a[N], n, m[N], maxx = -2e9; //带备忘录的递归，时间复杂度降低到O(N)；是最先进的书写 int find(int k) //当前第k个元素可以形成的最大 { if (m[k] != 0) //主要是回溯的时候避免重复计算，降低时间复杂度 return m[k]; if (k == 0) //递归探底，返回第一个元素（以第一个元素为起点） return m[0] = a[0]; //首发元素部署 m[k] = max(a[k], find(k - 1) + a[k]); //只要当前元素（新建起点） 或 前缀max（某个起点）+当前元素 //到0就return了，不会再向下找 return m[k]; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); find(n); //递归探底 // m[k]：以第k个元素结尾，所能形成的 max前缀和 //（起点在下层递归中自适应形成） for (int i = 0; i < n; i++) maxx = max(maxx, m[i]); printf("%dn", maxx); //把max扫出来 return 0; }
(1)算法思想
A.部署find(l,r)，意图返回区间l~r之间的最大公共子序列
递归边界在l=r时候，说明只有一个元素，那返回a[l] a[r]都可以
B.三分法思想·论当前最大公共子序列可能出现的位置
a.左侧区域 find(l,mid)
b.右侧区域 find(mid+1,r)
c.中间区域
以mid为切分，向左取得最长字段sum，向右同样取得sum
二者sum求和就是中间区域的最大子段和
（向左向右限制都不得超过当前lr范围）
以上为子状态分治拆分的结果，当前结果只能是以上三者之一
以上三个取得一个max就是当前l~r之间的最大公共子序列
关于时间复杂度
a. 单次求和复杂度O(1)
b. T(n)=2*T(n/2)+O(n)
两个是左右开递归的时间复杂度，n是中间部分的时间复杂度
c. 求解就是nlogn
//【最大子段问题】·分治算法P58 #include2-最大子段和 - 一维度DP 分析论#include using namespace std; const int N = 1e5 + 7, inf = -2e9; int a[N], n; int get_maxM(int l, int r) { int mid = l + r >> 1; int ML = inf, MR = inf, sum = 0; for (int i = mid; i >= l; i--) //中区左半部分最大值 { sum += a[i]; if (ML < sum) ML = sum; // Max_L } sum = 0; //恢复一下 for (int i = mid + 1; i <= r; i++) //中区右半部分最大值 { sum += a[i]; if (MR < sum) MR = sum; // Max_R } return ML + MR; //得出中区的max } int ans(int &a, int &b, int &c) //返回三个中的最大值 { a = max(a, b); a = max(a, c); return a; } int find(int l, int r) { // printf("%d %dn", l, r); if (l == r) //只有一个元素，无法切分的情况 return a[l]; int mid = l + r >> 1; int maxL = find(l, mid); //【左半区】递归 int maxR = find(mid + 1, r); //【右半区】递归 int maxM = get_maxM(l, r); //【中区】终章返回 return ans(maxL, maxR, maxM); //返回三者的最大值 } int main() { scanf("%d", &n); for (int l = 0; l < n; l++) scanf("%d", &a[l]); printf("%d", find(0, n - 1)); return 0; }
A.DP[k]：包含第k个元素的子段，最大和是多少
B.子状态分析：
a.前端衔接：a[k]+dp[k-1]
b.前端抛弃：a[k]
这个和上边的递归思想是一脉相承的
b方案就是舍弃前面的另立门户，a方案就是衔接前面的
二者取得max即可
C.注意事项：由于涉及到d[i-1]状态，所以数组从a[1]开始存储
#include2-最大子段和 - 零维度DP 分析论#include #include using namespace std; const int N = 1e5 + 7; int n, a[N]; int dp[N]; // dp[k]：包括a[k]在内，最长子段和是多少 void show() { for (int i = 1; i <= n; i++) printf("%d ", dp[i]); puts(""); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int sum = -2e9; for (int i = 1; i <= n; i++) { dp[i] = max(dp[i - 1] + a[i], a[i]); sum = max(sum, dp[i]); } //show(); printf("%d", sum); return 0; }
A.我们观察到当前dp[i]和dp[i-1]有关，到达第i次循环时候
B.认为当前dp就是dp[i]，而dp在没有【更新】之前是dp[i-1]
C.根本就用不到数组dp，只要零维度dp即可
#include3-01背包-二维 分析论#include #include using namespace std; const int N = 1e5 + 7; int n, a[N]; int dp; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int sum = -2e9; for (int i = 1; i <= n; i++) { dp = max(dp + a[i], a[i]); sum = max(sum, dp); } //内层的dp相当于dp[i-1] //我们最新外层更新的dp相当于dp[i] // show(); printf("%d", sum); return 0; }
1.宏观部署
F[i][y]：DP数组，属性为【最大价值】，表示只考虑前i个物品时，总重量不超过y的前提下，可以取得的最大价值是多少
N、m：n个物品，背包最多承重为m
W v：weight物品重量，value物品价值
2.状态表示
当前状态由前方状态承接而来，
A.选择第i个物品：
B.不选择第i个物品：
以上为两个子状态，我们最终要输出f[n][m]状态
（考虑前n个物品，总重量不超过n的最大价值）
3.状态转移方程
T1.如果装得下：
需要考虑选择和不选择，哪种价值会最大化？
A.选择，那就从【考虑前i-1个物品】【减去物品i的重量】的状态转移过来，价值是在上
一个状态的基础上+v（当前第i个物品的价值）：F[i][j]=f[i-1][j-w] + v
B.不选择，那就直接延承f[i-1][j]
以上两种方案需要进行比较，选择最大价值写入
T2.如果装不下：
那就不选择第i个物品，当前状态就直接延承考虑前i-1个物品
体积不超过j的状态：f[i][j] = f[i-1][j]
4.具体实践
需要关注一个问题，在考虑第i个物品时候，当前背包能不能装得下
三目运算符，会先让内部max执行之后再赋值
#include3-01背包-一维 分析论#include #include #include using namespace std; const int N = 1e3 + 7; int n, m, w, v, f[N][N]; //考虑前i个物品，容量不超过j的最大价值 // f[x][y]：考虑前x件物品中，当前使用的体积不超过y时，所能取得的最大价值 int main() { scanf("%d%d", &n, &m); //物品个数+背包大小 for (int i = 1; i <= n; i++) //寻访，每一件物品 { scanf("%d%d", &w, &v); //重量+价格 for (int j = 0; j <= m; j++) //寻访，每一寸体积 f[i][j] = j < w ? f[i - 1][j] : max(f[i - 1][j], f[i - 1][j - w] + v); }//如果背包够装，就取max；装不下就只能延承i-1不添加新物 printf("%d", f[n][m]); return 0; }
5.维度压缩（优化）
A.思想来源：
我们发现f[i][j]只与f[i-1][j]上一层有关，我们在进入下一层循环的时候，在算法执行之前f中存储的就是上一层i-1的数据，我们新算出来的f[i]覆盖进去就可以了
B.改造思路 对f的意义进行优化定义，压缩成一维度
F[x]：体积不超过x时的最大价值
C.注意事项 为什么是从大到小枚举？
简单来说，因为我们【当前状态】的生成需要使用到【之前状态】，会调动f[i-v]，如果我们从小到大进行枚举，f[小数字]会被率先更新为【当前状态】（覆盖掉了），那么我们算到f[大数字]时候需要调动f[小数字]，但是此时的f[小数字]已经不是【之前状态】了，出现异常覆盖！
为了确保 f[j-v[i]]这个状态没有更新过，是i-1层的
而不是出现用本层更新过的数据，认为是上一层的数据来参与计算
出现 “串联”；所以让j从大到小枚举
j在右边，j-v[i]在左边；一路向左推过去，只是更新最右侧的j
即可确保右侧更新是进行比较的【左端点】是来自i-1层
思想上，如果认为序列n很长，我们从左向右推进
更新右端点，采用的【左端点】，必然会遇到第i层（本轮）已经更新过的右端点，这就不对了
D.优化论
从大到小枚举从【最大体积】枚举到【当前物品体积】即可，可保障当前背包容积一定能够装下当前物品，就不要再去搞三目什么的了
E.状态转移论
F[j]相当于f[i][j]，只要考虑f[i-1][j]和f[i-1][j-w]+v的情况即可，取max
二维压缩的话把第一维度的i去掉就可以了，新覆盖进去的就相当于i
里面存储的相当于i-1层
#include4-独立任务最优调度 - 二维 分析论#include #include #include using namespace std; const int N = 1007; int n, m; int f[N]; int main() { scanf("%d%d", &n, &m); // n个物品，m的背包体积 for (int i = 1; i <= n; i++) { int v, w; // v是价值，w是体积 scanf("%d%d", &v, &w); for (int j = m; j >= v; j--) //从全体积开始考虑，以装的下为标准 f[j] = max(f[j], f[j - v] + w); //【至少能装得下1个】，才考虑要不要更新 //否则就是【延承】i-1位置的数据 } printf("%d", f[m]); return 0; }
1.问题论述
有两台机器AB，需要批改n个作业，每个作业给不同的机器所需要的批改时间是不一样
的，分别记作a[x] b[x]；现在给出这一组作业，输出两台机器完成批改所需的最短时间。
2.状态表示
A.集合表示
F[x][y]：处理完前x作业，A机器总用时为y时，B机器最低用时
B.集合属性
取得min（B机器最低用时），分别用两个for循环进行状态更新，第一层遍历所有作
业，第二层遍历A所有可能的时间状态
C.额外说明
a)关于A机用时状态
由于第二维度需要遍历A机器所有可能的时间状态，所以我们在全局变量部署一个
time_A，作为所有作业都给A批改时的A机总用时
b)关于真实用时
最终完成批改的时候，A机器和B机器各自耗时或为不同，需要取得二者最大
值为所有任务完成用时
3.状态转移
状态论：我们认为前i-1个作业全部批改完成，现在第i个作业给谁？
A.给A机器：那么B机器时间不变（F直接延承）从哪里延承？
思考认为，此时（处理完成第i个作业）和（第i个作业还没处理） 时候的B机器用时是
【一致的】，也就是：F[i][j]=f[i-1][j-a[i]]
（A机器减去第i个作业用时·前状态）
（【A机尚未处理第i个作业时的机器B用时】=【A机处理完成第i个作业时的机器B用时】）
B.给B机器：那么B机器需要加上（处理第i个作业所需用时）
思考认为，此时A机用时是不变的（第二维度j不变），也就是
F[i]][j]=f[i-1][j]+b[i]
（B处理前i-1个作业用时）+（B处理第I个作业用时）
4.注意事项·朴素
数组地址不能是负数，需要注意当前作业给A机器用时，如果超过A机器总用时j时候，A机器是没法处理这个作业的，只得交由B机器处理。
否则就是AB状态都计算一下，取得min来更新f[x][y]
全部处理完成时候，真实时间需要另外写一个for循环，枚举AB机器在阶段状态的用时，取得max真实时间之后，得出全局最小真实时间
5.时间复杂度
两层循环O(n^2)，实际上会比n²大一点，因为第二维度遍历的是A机器全部时间状态，通常情况下比n大
//独立任务最优调度问题 #include4-独立任务最优调度 - 一维 分析论#include #include #include using namespace std; const int N = 1e4 + 7; int a[N], b[N], f[N][N]; int A_all, n, min_t = 0x3f3f3f; int dp() { for (int i = 1; i <= n; i++) //遍历，所有作业 for (int j = 0; j <= A_all; j++) //遍历，A机所有时间 { int ta = f[i - 1][j - a[i]]; int tb = f[i - 1][j] + b[i]; //交由A机处理时候，B机延承（A尚未处理第i个作业）时的B机用时 //交由B机处理的时，A机用时不变，B机用时+处理第i个作业的用时 //第i个作业耗时在A机（当前最大耗时）的承受范围之内，取得min //否则只得交由B机处理 f[i][j] = a[i] > j ? tb : min(ta, tb); } for (int i = 0; i <= A_all; i++) //扫一遍，A所有可能的时间 { int t = max(f[n][i], i); // A机用时为i，此时B机用时为f，二者取max是实际完成的用时 if (min_t > t) //意图取得min min_t = t; } return min_t; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), A_all += a[i]; for (int i = 1; i <= n; ++i) scanf("%d", &b[i]); printf("%dn", dp()); return 0; }
7.压缩优化
A.观察发现
当前f[i][j]和上一层的f[i-1][j]是有关的，不涉及跨层，那么就可以用类似于01背包优化的办
法给他第一维度搞掉；我们当前计算得出的就是当前的f[i][j]，在计算开始前f里面存的就
是i-1层的内容
B.进化思想
F[x]：A机器用时最大为x时候，B机器的最低用时
8.进化优势
A.节省了不必要的空间，实现了空间优化（时间复杂度不变）
B.能够处理更大规模的问题
如果是二维f，N最多=1e4+7，再多就爆堆栈了
现在一维度f，N最多=1e7+7，可以处理更多更复杂的状态
9.注意事项·进化
和01背包一样，因为这里需要调用【上层f[小数字]状态】，所以部署为从大到小扫
描，避免出现错误覆盖，导致对【非上层状态】的引用，导致错误结果。
类似于01背包的思想，为什么我们这里j不是限制到a[i]来确保这个任务是可以交由A
机器处理的呢？
因为这违背了转换等价性原则。
在a[i]>j的部分，我们原则上是要部署tb=f[i-1][j]+b[i]的
如果把这部分不进行计算（就是限制最小到a[i]） 那么我们实际上是部署了tb=f[i-1][j]
01背包之所以能进行限制，是因为他不限制的时候，状态方程刚好是上边这个
我们这个问题时要把b[i]给加上。
//独立任务最优调度问题 #include5-哈夫曼编码 分析论 代码区 6-01背包-递归回溯 分析论 代码区 6-01背包-迭代回溯 分析论 代码区 7-旅行售货商 分析论 代码区 8-最小重量机器 分析论 代码区#include #include #include using namespace std; const int N = 1e7 + 7; int a[N], b[N], f[N]; int A_all, n, min_t = 0x3f3f3f; int dp() { for (int i = 1; i <= n; i++) //每个作业 for (int j = A_all; j >= 0; j--) // A机器所有时间状态 { int ta = f[j - a[i]]; int tb = f[j] + b[i]; f[j] = a[i] > j ? tb : min(ta, tb); } for (int i = 0; i <= A_all; i++) //扫描，处理完成N个作业时候， { int t = max(f[i], i); // A B机器中最大耗时为真实时间 if (min_t > t) //取得真实时间的最小值 min_t = t; } return min_t; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), A_all += a[i]; for (int i = 1; i <= n; ++i) scanf("%d", &b[i]); printf("%dn", dp()); return 0; }
