等我写完快排实验我才发现实验1是二分搜索不是快速排序tnnd都写完了舍不得删
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上
这个我也不知道怎么说，看大家自己的悟性，我是这么理解的
这是我在整数二分搜索中参悟的思想
代码区#include
#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
//思想上和二分查找是一脉相承的
/* S1左向右，S2右向左；最终数轴位置 S2在左S1在右
l+r 除以2，那么 mid踩在靠左侧 R 【左侧S2】【右侧S2+1】
l+r+1除以2 那么 mid踩在靠右侧 L 【左侧S1-1】【右侧S1】
*/
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;
}
/*
样例：对于取【中间点】【边界点】
10
49 59 88 37 98 97 68 54 31 3
样例：对于【do while】格式修改的；超时
30
128 294 133 295 175 8 232 248 241 164 11 60
238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216
*/
/*o(nlogn)
速度快，但是不稳定（相同数值的相对位置在排序前后或发生变化）
额外空间小，容易实现，书写简单（唯一的缺点）
*/
/*改S1报错
10
49 59 88 37 98 97 68 54 31 3
*/ 使用queue临时存一下l和r，先进去的一定是【大区间】，向下递归的【小区间】存后边
网上找代码真是太难受了，写的又复杂又不直观，学习思想后自己写更舒服
queue是从宏观到微观，宏观工作完成了才会向下递归（d出queue）
不能使用stack，因为他会在【没有完成工作】的情况下探底
#include
#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()) //非空的时候，依次d出
{
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 %d\n", 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
#include
#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
/*
二分搜索，应用于具有单调性的序列之中
现有一串不减序列，给到n个数字和m个询问
数组内编号0~n-1
输出所询问数字的启止范围
如果不存在输出-1 -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 -1\n");
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("%d\n", r);
}
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
结束的时候看一下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
*/ 稍微改造一下就可以了，思路和上边是一样的，只是while控制改成边缘返回条件罢了
同样通过了ACWING的测试
#include
#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 -1\n");
continue;
}
int r = getR(t, 0, n - 1);
printf("%d %d\n", l, r);
}
return 0;
} #include
#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;
}
/*
6
-2 11 -4 13 -5 -2
*/ (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函数
#include
#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("%d\n", maxx); //把max扫出来
return 0;
}
/*
6
-2 11 -4 13 -5 -2
6
-2 1 -4 -13 -5 -2
如果全是负数的话，就是扫描一个最大的数值出来
*/
(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
#include
#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 %d\n", 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;
}
/*
最大子段有三种出现情况
1.全在左半区 maxL
2.全在右半区 maxR
3.踩在mid上 从中间向两侧延伸的max
*/
/*
7
-2 -11 -4 -13 -1 -2 -5
6
-2 -11 14 -13 -5 -1
*/ A.DP[k]：包含第k个元素的子段，最大和是多少
B.子状态分析：
a.前端衔接：a[k]+dp[k-1]
b.前端抛弃：a[k]
这个和上边的递归思想是一脉相承的
b方案就是舍弃前面的另立门户，a方案就是衔接前面的
二者取得max即可
C.注意事项：由于涉及到d[i-1]状态，所以数组从a[1]开始存储
#include
#include
#include
using namespace std;
const int N = 1e5 + 7;
int n, a[N];
int dp[N]; // dp[k]：包括a[k]在内，最长子段和是多少
/*
由两种子状态转移来
dp[k-1]+a[k]
a[k]
两个取max来
*/
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;
}
/*
6
-2 11 -4 13 -5 -2
*/ A.我们观察到当前dp[i]和dp[i-1]有关，到达第i次循环时候
B.认为当前dp就是dp[i]，而dp在没有【更新】之前是dp[i-1]
C.根本就用不到数组dp，只要零维度dp即可
#include
#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;
}
/*
6
-2 11 -4 13 -5 -2
*/ 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执行之后再赋值
#include
#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时，所能取得的最大价值
/*
状态转移方程、
1.不选择：f[x][y]=f[x-1][y] 直接不考虑第x个物品，体积不变
2.选择：f[x][y]=f[x-1][y-w[x]]+v[x] 减去第x个物品的体积，加上价值
默认不选择，如果体积OK考虑选择，二者取一个max
最终结果在f[x][0-v]中取出max即可
*/
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;
}
/*
01背包
物品只能选一次，选或者不选
选只能整个选
思想·苏晓辉のDP思想（建议多做题？）首发思考二维
0.状态表示：【前i个物品】【某种限制】(如体积等)
坐标表示什么集合？
考虑前i个物品，总体积不超过j；的方案的最大值 集合
存的数值和集合之间是什么关系？
方案集合中的最大价值
1.状态计算 固定套路，【看最后一个或几个物品的不同点】
f[i][j]的子集划分（子集首先要满足f[i][j]限制）
（子集通过某种变化，可以转移为当前的状态）
A.选择第i个物品后体积=j：f[i-1][j-w[i]]+v[i]
（前i-1个物品中，总体积小于j-w[i]的最大价值，再加上选中第i个物品）
减去重量，获得价值。
B.不选择第i个物品体积=j：f[i-1][j]
（只考虑前i-1个物品，总体积小于等于j）
二者取max（B方案启用需要判断，背包体积是否能容下）
默认选择第一方案
大致一个感知：前面随便选，最后考虑是否包含物品i即可
在递推过程中每一步都取得最优解，子问题也拿到最优解
最终得出全局的最优解
3.时空优化 看递推公式
发现只需要用到上一层的情况
所以二维降维一维
4.优化控制
从大到小，防止出现“串联”
j在右侧侧j-w在左侧；更新点是右侧的j
从大到小递推，可以保障j-w都是上层i-1的数字
从小到大递推，你访问的j-w可能是前几轮更新已经更新过的变成了第i层而非i-1层
DP优化过程要保证前后代码等价
*/
/*
01背包：每个物品最多只取得一次
完全背包：每个物品可以取得无限次
多重背包：每个物品最多取得Si个（每个物品有多个副本）
优化问题：
分组背包问题：多分组每组有若干物品，每组里边只能选1个
*/ 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层
#include
#include
#include
#include
using namespace std;
const int N = 1007;
int n, m;
int f[N];
/*
二维改进，发现当前层状态只和上一层有关
那么可以压缩为一层即可
f[x]：所有体积小于等于x的方案，取得的最大价值
*/
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位置的数据
} /*
为什么是从大到小枚举？
为了确保 f[j-v[i]]这个状态没有更新过，是i-1层的
而不是出现用本层更新过的数据，认为是上一层的数据来参与计算，出现 “串联”
所以让j从大到小枚举
j在右边，j-v[i]在左边；一路向左推过去，只是更新最右侧的j
即可确保右侧更新是进行比较的【左端点】是来自i-1层
思想上，如果认为序列n很长，我们从左向右推进
更新右端点，采用的【左端点】，必然会遇到第i层（本轮）已经更新过的右端点
这就不对了*/
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大
//独立任务最优调度问题
#include
#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("%d\n", dp());
return 0;
}
/*
6
2 5 7 10 5 2
3 8 4 11 3 4
*/
/*
状态表示
集合：f[i][j]全局总用时：处理完成前i个作业，A机器总用时为J时，机器B的最低用时
属性：min I：第I个作业 J：A总用时 内存：B用时
真实用时t=max(j,f[n][j])；//处理完成n个作业，.
状态计算
子集分析：边界情况，认为i-1个作业处置完毕，看第i个作业给谁处理
A.给A机器处理：f[i][j]=f[i-1][j-a[i]]，B机器用时没变
A机处理第i个作业前，B机用时；不变！
B.给B机器处理：f[i][j]=f[i-1][j]+b[i]
（B处理前i-1个作业用时）+（B处理第I个作业用时）
（A机没有新任务，时间不变）
注意一个边界，循环J时候，如果J=a[i]）
那么第I个作业只能给到B机器处理
否则就AB中取得min进行转移
状态转移：
状态不合法：由B转移得来， 否则：AB中取得min进行转移
f[i-1][j-a[i]]：第I作业给到A处理，B机器总用时不变，延承
f[i-1][j]+b[i]：第I作业给到B处理，A机器总用时不变，加上B处理第I作业的情况
初始化：部署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]给加上。
//独立任务最优调度问题
#include
#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("%d\n", dp());
return 0;
}
/*
6
2 5 7 10 5 2
3 8 4 11 3 4
*/
/*
状态表示
集合：f[i][j]：处理完成前i个作业，A机器总用时为J时，机器B的最低用时
属性：min I：第I个作业 J：A总用时 内存：B用时
真实用时t=max(j,f[n][j])；//处理完成n个作业，.
状态计算
子集分析：边界情况，认为i-1个作业处置完毕，看第i个作业给谁处理
A.给A机器处理：f[i][j]=f[i-1][j-a[i]]，B机器用时没变
（【A机尚未处理第i个作业时的机器B用时】=【A机处理完成第i个作业时的机器B用时】）
B.给B机器处理：f[i][j]=f[i-1][j]+b[i]
（B处理前i-1个作业用时）+（B处理第I个作业用时）
（A机没有新任务，时间不变）
注意一个边界，循环J时候，如果J=a[i]）
那么第I个作业只能给到B机器处理
否则就AB中取得min进行转移
状态转移：
状态不合法：由B转移得来， 否则：AB中取得min进行转移
f[i-1][j-a[i]]：第I作业给到A处理，B机器总用时不变，延承
f[i-1][j]+b[i]：第I作业给到B处理，A机器总用时不变，加上B处理第I作业的情况
初始化：部署0即可，没开始处理都不耗时
*/ 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）