2021十月暂记（1）

2021.10.04

T1 性质（打表发现性质） A’

T2 二分，DP，矩阵优化

充分并正确地利用周期性减少时间复杂度
机器人巡逻有周期，而且机器人数量不多，周期短，通过对它们周期求 lcm 求得一个大周期，然后将求出一个大周期中每个时刻哪些点能走，哪些点不能走。
二分最大边权，判定在这个最大边权下，能否恰走到终点
设 $f(i,j)$ 表示从 $s$ 开始，到 $i$ 时刻，$j$ 能否到达。
先算 0 时刻到第一个大周期结束的结果，DP 暴力判定即可。
然后算第一个大周期结束到下一个大周期结束的每个时刻各个点能否可达。
以两个大周期间的计算结果作为普遍参考，默认接下来全部按照可达的方式跑图，那么可以省略中间所有重复跑图的过程，令 $tmpk=k\mathrm{m}\mathrm{o}\mathrm{d}(T+1)+1$ ，可以知道最后还剩 $tmpk$ 的时间要恰好走到终点 $t$ ，这时所有可达状态与先前是一样的，所以判断 $f(tmpk,t)$ 是否为 1 即可。

T3 数论，二分，枚举，统计技巧：桶计数，前缀和…

2021.10.05

T1 数学，9 位小数相乘爆精度，乘上 $10^9$ 转为整数，问两两相乘能否为整数，则统计对于 $a$ 中转为整数后的 $2^x$ 和 $5^y$ ，统计 $b$ 中转为整数后的 $2^a$ 和 $5^b$ ，相乘后的数中的因子，有 $10^{\min (x+a,y+b)}$， 所以当 $\min (x+a,y+b)⩾18$ 时，说明 $a\times b$ 是整数。

2021.10.06

T1 DP

观察题目所给操作的性质，首先是熟悉的向右向下走的限制，然后是任选子矩阵取反的操作，当路径中出现 1 的时候才需要取反操作，而且当某几步呈单次折线状且路径上全是 1 的时候可以使用一次取反操作使路径上的 1 变为 0
那么考虑 DP ，设 $f(i,j)$ 表示走到 $(i,j)$ 的时候所需的最少操作数，考虑什么情况下向右走一步必须使用一次操作，什么情况下向左走一步必须使用一次操作。
那么有：
$$f(i,j)=\min \{\begin{array}{l}f(i-1,j)+[a_{i,j}=1且a_{i-1,j}=0]\\ f(i,j-1)+[a_{i,j}=1且a_{i,j-1}=0]\end{array}$$

T2 树的性质

AT2304 [AGC010C] Cleaning
给出树上每个点被覆盖的次数，问是否存在一种若干条叶子结点间的路径覆盖的方案使得给出的树上覆盖次数合法。
考虑树的问题，要考虑父子关系和祖孙关系。
设某一结点覆盖次数为 $a_u$ ，那么这 $a_u$ 条路径可能向上延伸，可能到此为止，设向上延伸有 $f_u$ 条，到此为止有 $g_u$ 条，易得 $a_u=f_u+g_u$
设其所有儿子向上延伸有 $s_u={\sum }_{v\in so{n}_u}{f}_v$ 条，那么可以知道
$$\begin{gathered} 2g_u+f_u=s_u \\ {g}_u=a_u-f_u \\ {f}_u=2a_u-s_u \end{gathered}$$
特别的，叶子结点 $f_u=a_u$，由此算出所有结点的 $f_u$
为了判定是否存在合法方案，考虑推算出来的量之间应当满足的关系
由于 $f_u$ 由 $a_u$ 和 $s_u$ 推算出来，所以考虑他们之间应满足的关系
首先
$0⩽f_u⩽a_u$ ，向上延伸的路径数不可能超过覆盖此点的次数
${\max }_{v\in so{n}_u}{f}_v⩽a_u$，这个是 $\forall v\in so{n}_u,f_v⩽a_u$ 的等价条件，由此省去不必要的枚举判断

T3 强连通分量，图论，性质

AT3945 [ARC092D] Two Faced Edges
比较容易发现的性质：

• 当一条边在一个强连通分量中时，如果存在别的路径可以替代它，那么将它反向后不改变强连通分量数目
• 当一条边在一个强连通分量中时，如果不存在别的路径可以替代它，那么将它反向后，会改变强连通分量的数目
• 当一条边不在一个强连通分量中时，如果存在别的路径可以替代它，那么将它反向后会改变强连通分量的数目
• 当一条边不在一个强连通分量中时，如果不存在别的路径可以替代它，那么将它反向后不会改变强连通分量的数目

判断边是否在强连通分量中很简单，可以使用熟悉的 Tarjan 算法。
问题在于如何判定是否存在别的路径可以代替一条边：
暴力方法就是暴力删边然后 DFS 看看是否可以到达原来那条边的终点，时间复杂度 $O(n{m}^2)$。
但是我们要优化时间复杂度，考虑到如果一条边可以被别的路径替代，那么如果将这条边放在最后遍历，一定发现这条边的终点先前已经被遍历过，但是如果暴力将这条边放在最后，我们发现这样的做法无异于暴力。
我们想想如何发现存在不经过这条边的路径比这条边线到达这条边的终点。
考虑借助 DFS 搜索树解决问题，我们发现，如果不存在这样的路径，那么这条边的终点一定在以这条边起点为根的 DFS 搜索树中深度为 1 的位置。
为了保证没有别的路径，我们可以改变边的遍历顺序，先前的搜索都是沿邻接链表正向遍历，所以无法得知这条边后面的边是否在替代路径中，所以考虑再进行一次沿邻接链表逆向的顺序遍历，这样就得到两棵 DFS 搜索树。
综上所述，我们只要按两种顺序 DFS ，然后查看与根直接相连的边的终点的深度是否始终为 1 ，就可以判断这条边是不是不可替代。
时间复杂度 $O(nm)$

2021.10.07

T1 字符串，性质 A

T2 计数，组合数学，性质 A

容易发现 $k⩽8$ ，而且有一个显而易见的性质：能回到 1 的路径一定在前 $k$ 个点里，所以前 $k$ 个点一定填 1~k ，后 $n-k+1$ 个点一定填 n-k+1~n。
那么对于前 8 个位置暴搜即可，后面的随便填，快速幂计算方案数
最后方案数相乘即得答案

T3 计数，DP，优化

计数问题常通过 DP 解决，那么对于此题，设 $f(i,j)$ 表示搭了 $j$ 次电梯后，来到楼层 $i$ 的方案数。显然有：
$$f(i,j)=\sum _{k\in 可到达i的楼层}f(k,j-1)$$
然而实际实现的时候，时间复杂度高达 $O(n^3)$ 。
考虑如何优化算法，不难发现，在转移的过程中复杂度比较大。
可以考虑优化转移方程，也可以考虑改变转移顺序，或者用技巧或数据结构高效维护 DP 的值。
通过题目的条件 $|x-y|<|x-B|$ ，我们可以分类讨论一下：

• $y>B$ 时，$f(x,i),x\in [n,y)\cup (\lfloor \frac{y+B}{2}\rfloor +1,y)$ 对 $f(y,i+1)$ 有贡献
• $y<B$ 时，$f(x,i),x\in [1,y)\cup (y,\lfloor \frac{y+B}{2}\rfloor )$ 对 $f(y,i+1)$ 有贡献

所以可以考虑用前缀和优化转移带来的复杂度，那么就可以做到 $O(1)$ 转移，总体时间复杂度降为 $O(n^2)$

10.9

P1266 速度限制、P4568 [JLOI2011]飞行路线 （分层思想）

两道最短路分层的题目，这里的分层是指将图的不同状态全部生成即得到不同的层。
主要应用于在求答案过程中图的状态会发生改变的题目中。
主要操作方法：将图的所有状态生成，然后抓住层与层之间的关系，在层与层之间连边，然后就可以跑最短路

P3522 [POI2011]TEM-Temperature （单调队列）

求满足 $R_i⩾\max L_j$ 的最大连续区间个数，用单调队列解决。
最开始想到一个错误的 DP ，设 $f(i)$ 表示前 $i$ 个区间中最多合法连续区间的个数，转移方程
f ( i ) = { f ( i − 1 ) + 1 R i ⩾ g ( i − 1 ) 1 R i < g ( i − 1 ) g ( i ) = { max ⁡ { g ( i − 1 ) , L i } R i ⩾ g ( i − 1 ) L i R i < g ( i − 1 ) f(i) = begin{cases} f(i - 1) + 1&R_igeqslant g(i - 1)\1&R_i< g(i - 1) end{cases}\ g(i)= begin{cases} max{g(i - 1),L_i}&R_igeqslant g(i - 1)\L_i&R_i< g(i - 1) end{cases}\ f(i)={f(i−1)+11​Ri​⩾g(i−1)Ri​<g(i−1)​g(i)={max{g(i−1),Li​}Li​​Ri​⩾g(i−1)Ri​<g(i−1)​
错误在于没有考虑到当当前区间无法与前面最大连续的区间相容时，一刀切地抛弃前面所有区间，然而前面与 $i$ 连续的满足 $R_i⩾L_j$ 的区间还是可以与当前区间相容。
考虑更新的时候，直接抛弃整段区间的做法是错误的，那么就要从前往后逐段抛弃，这个操作有些尺取法的味道。
然后又考虑到最前面的一些区间可能满足 $R_i⩾L_j$，即我们希望从前面开始就碰到不合法的区间，然后删除这些区间，从这里可以考虑到维护 $L_j$ 的单调不上升的性质，才可以逐段抛弃。
综上所述，我们可以考虑用单调队列维护。
令队列 q 维护 $L_j$ 的单调性，队列 pos 维护 $j$ ，在加入新元素的时候，从队头开始检查，如果无法满足合法性，那么就弹出队头元素。
然后队列中剩下的区间是可以和当前区间相容的，那么计算一次答案， a n s = max ⁡ { a n s , i − p o s ( h e a d ) + 1 } ans = max{ans,i-pos(head) + 1} ans=max{ans,i−pos(head)+1}。
然后维护 $L_j$ 的单调性，加入新元素。
这时发现有一个问题，就是在维护 $L_j$ 单调性的时候，会删除合法的区间，我们可以令 pos 维护最早合法区间的位置，然后就可以正常更新答案了。
核心代码：

for(int i = 2;i <= n;i ++)
{
	tmp = i;
	for(;r[i] < ql[head] && head <= tail;) head ++;//维护合法性
	if(head <= tail) ans = max(ans,i - lst[head] + 1);//更新答案
	for(;l[i] > ql[tail] && head <= tail;) tmp = lst[tail],tail --;//维护单调性，记录最早的合法区间
	tail ++;ql[tail] = l[i];//加入元素
	lst[tail] = min(tmp,(ll)i);
}

P1613 跑路 （建立等效边）

首先题面有几个提示的点

• 跑路器可以 1s 跑完 $2^k$
• 路径长度不会超过 $2^{31}-1$
• $n⩽50$

关注 $2^k$ ，我们不仅仅可以想到状态压缩，现在也要学会想到倍增法。
考虑到直接跑最短路会出错，因为路径长度在增加的过程中，其二进制中 1 的个数不是随之增加的，所以我们要考虑将这些长度为 $2^k$ 的路径用长度为 1 的边代替，这时候就用上了建立等效边的技巧。
另外，我们要知道 $2^k+2^k=2^{k+1}$ ，那么我们可以考虑用 Floyd (DP) 来预处理这些等效边，设 $G(i,j,k)$ 表示 $i$ 到 $j$ 的路径中是否存在一条长度为 $2^k$ 的边。

对于一条边 (u,v) ，令 G[u][v][0] = 1;
for(int t = 1;t <= 64;t ++)
	for(int k = 1;k <= n;k ++)
		for(int i = 1;i <= n;i ++)
			for(int j = 1;j <= n;j ++)
				if(G[i][k][t - 1] && G[k][j][t - 1])
					G[i][j][t] = 1,dis[i][j] = 1;//建边且更新G

处理完这些等效边后，我们就不必考虑数出路径长度二进制下 1 的个数的问题了，我们现在依靠着这些等效边和原边跑一边最短路就可以得到答案了。

for(int k = 1;k <= n;k ++)
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= n;j ++)
			dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
ans = dis[1][n];

再次回顾这道题，当我们发现图中出现了非常规计算路径长度的方式时，我们可以考虑将这些非常规计算的路径长度预处理，然后建立常规的等效边，这样我们就可以在图上顺畅地跑最短路了。

10.10

CF1442D Sum（性质，分治解 01 背包）

最开始想着将所有数组的前缀和求出来，然后跑分组背包，时间复杂度 $O(n{k}^2)$ ，炸裂。
然后又是看题解积累经验的一天…
我也不知道大家怎么想出或者发现一个结论：存在一个最优解，使得至多只有一个数组没有选完，其它数组要么不选要么选完。
证明不是很难：
假设有两个数组没有选完，$a_n$ 选了 $a_1$~$a_i$ ，$b_m$ 选了 $b_1$~$b_j$，然后分类讨论：

• 若 $a_i<b_j$，因为数组不降，那么不如将这 $i$ 个选择机会留给剩下的 $b$
• 若 $a_i>b_j$，同理，不如将 $j$ 个选择机会留给剩下的 $a$
• 若 $a_i=b_j$，同理，无论将 $i$ 个机会留给 $b$ 抑或是将 $j$ 个机会留给 $a$ 都比当前解更优

然后根据这个结论得到做法：枚举不全选的数组，然后剩下的 01 背包。
可以考虑使用分治算法优化时间复杂度，不然直接跑也是 $O(n{k}^2)$ 。
这里的分治算法设计意思是分治枚举不全选的数组，每次考虑 $[l,r]$ 中的数组，然后不全选的数组要么在 $[l,mid]$ 的数组中，要么在 $[mid+1,r]$ 的数组中，前往解决子问题之前，先将另一半 DP 完，最后当枚举的区间只剩一个元素，就意味着我们令这个数组不全选，完成最后的 DP 并更新答案。
时间复杂度降至 $O(nk\log n)$ 可以通过本题。
核心代码：

void dp(int l,int r)//枚举不全选的数组
{
	if(l == r)//枚举到一个不全选的数组
	{
		for(int i = 0;i <= min(k,ti[l]);i ++)//最后一次 DP
			ans = max(ans,f[k - i] + res[l][i]);//更新答案
		return ;
	}
	int mid = ((l + r) >> 1);
	ll tmp[3005] = {0};
	for(int i = 0;i <= k;i ++) tmp[i] = f[i];//记录当前的 DP 值，备用
	for(int i = l;i <= mid;i ++) //先处理另一半
		for(int j = k;j >= ti[i];j --)
			f[j] = max(f[j],f[j - ti[i]] + sum[i]);
	dp(mid + 1,r);//然后再去解决另一半
	for(int i = 0;i <= k;i ++) f[i] = tmp[i];//恢复原先的 DP 值
	for(int i = mid + 1;i <= r;i ++)//同理先处理另一半
		for(int j = k;j >= ti[i];j --)
			f[j] = max(f[j],f[j - ti[i]] + sum[i]);
	dp(l,mid);//再解决另一半
	return ;
}

我也不知道大佬们是如何发现题目中的结论的，但是在我看来，发现性质的手段之一是推理，另一重要手段是通过大量事实，即手玩样例猜测结论，而后证明。当我们发现没有思路解题，或者没有思路优化算法的时候，除了运用技巧以外，还要发掘题目中的结论，辅助算法设计。

P3622 [APIO2007] 动物园 （状态压缩优化状态设计）

“好题”
细细品味一下…
题面很长，要耐心看完，看完以后就是一头雾水。
既然是最优化问题，考虑 DP ，我们发现，从 1 到 n 是一种可能的 DP 顺序，考虑 $f(i)$ 表示处理到第 $i$ 个位置能使多少小朋友开心，然而这个状态无法完整表达所需的信息，我们需要额外增加一些记录的信息。
突破口在于那个固定的可视范围 $5$ ，这时候状态压缩就派上了用场，设 $f(i,S)$ 表示处理到第 $i$ 个位置，且 $[i,i+4]$ 的动物状态为 $S$ ，然后考虑如何转移。
不难发现，处理第 $i$ 个位置之前，先处理了 $i-1$，那么就有
f ( i , S ) = max ⁡ { f ( i − 1 , S ′ ) } + Δ f(i,S)=max{f(i - 1,S')} + Delta f(i,S)=max{f(i−1,S′)}+Δ
我们发现 $S^{\prime }$ 的前 4 位与 $S$ 的前 4 位相同，所以能转移到 $S$ 的 $S^{\prime }$ 实际上只有两种，然后考虑计算 $\Delta$ ，$\Delta$ 就是在 $i$ 位置开始有视野的小朋友中，在动物状态为 $S$ 的情况下，最多有多少小朋友开心，可以通过预处理计算。
于是就有
f ( i , S ) = max ⁡ { f ( i − 1 , ( ( S & ( ( 1 < < 4 ) − 1 ) ) < < 1 ) , f ( i − 1 , ( ( S & ( ( 1 < < 4 ) − 1 ) ) < < 1 ∣ 1 ) } + s u m ( i , S ) f(i,S)=max{f(i-1,((S&((1<<4)-1))<<1),f(i-1,((S&((1<<4)-1))<<1|1)}+sum(i,S) f(i,S)=max{f(i−1,((S&((1<<4)−1))<<1),f(i−1,((S&((1<<4)−1))<<1∣1)}+sum(i,S)
其中，$sum(i,S)$ 是 $\Delta$ 的意义。
为计算 $\Delta$ ，利用小朋友的信息统计，这里可以用到一个小技巧，根据题目，小朋友开心的条件是以下之一：

• 至少有一个不喜欢的动物移走
• 至少有一个喜欢的动物留下

那么用二进制数fear,like记录小朋友对面前这五个动物的态度，对于fear，1 表示不喜欢，对于 like，1 表示喜欢，然后枚举状态 sta的时候，sta中 0 表示移走，1 表示留下，如果 (fear&(~sta))>0||(like&sta)>0那么这个小朋友就可以统计到$sum(i,j)$ 中。
最后由于动物园是个环，所以枚举到 N 的状态要与 0 的状态一致，所有的计算结果要相容，所以最开始先枚举最终的结束状态 $k$，然后对 $f(0,S)$ 初始化全部赋极小值表示不可达状态，$f(0,k)$ 赋值为 0，然后才开始 DP ，最后以这个状态结束的答案为 $f(N,k)$

#include<iostream>
#include<cstdio>

using namespace std;
const int inf = 0xfffffff;
const int tot = (1 << 5 );
int N,C,E,F,L,X;
int fear,like,sum[50005][tot + 5];
int f[50005][tot + 5];//f(i,S) 表示枚举到 i ，[i,i+4]状态为 S 的开心的小朋友的最大人数 
int ans;

int main()
{
	scanf("%d%d",&N,&C);
	for(int i = 1;i <= C;i ++)
	{
		scanf("%d%d%d",&E,&F,&L);
		fear = 0;like = 0;
		for(int j = 1;j <= F;j ++)//fear
		{
			scanf("%d",&X);
			X = (X - E + N) % N;
			fear = (fear | (1 << X)); 
		}
		for(int j = 1;j <= L;j ++)//like
		{
			scanf("%d",&X);
			X = (X - E + N) % N;
			like = (like | (1 << X));
		}
		for(int j = 0;j < tot;j ++)
			if( ((fear&(~j)) > 0)||((like & j) > 0) )//0撤走 1留下 
				sum[E][j] ++; //sum 表示[E,E+4]中动物的状态为j时，视野在[E,E+4]的能够开心的小朋友人数 
	}
	for(int endst = 0;endst < tot;endst ++)//枚举结束状态 
	{
		for(int j = 0;j < tot;j ++)
		{
			if(j != endst) f[0][j] = -inf;//枚举到 N 相当于枚举到 0 ，满足题目环的条件，使所有位置的计算结果相容 
			else f[0][j] = 0;
		}
		for(int i = 1;i <= N;i ++)
			for(int j = 0;j < tot;j ++)
				f[i][j] = max(f[i - 1][(j&((1<<4)-1))<<1],f[i - 1][((j&((1<<4)-1))<<1)|1]) + sum[i][j];
		ans = max(ans,f[N][endst]);
	}
	printf("%d",ans);
	return 0; 
}

总结：不难发现，除了纷繁复杂的细节以外，本题最重要的核心思想是利用状态压缩优化状态设计。如果一开始就看了标签，那么就会以定势思维的方式思考，想如何用二进制状态 DP。然而本题一开始就是正常的 DP 思维，后面设计状态的时候由于要增加记录的信息，才想到利用状态压缩巧妙设计状态，打破了二进制数表达一切的定势思维。所以我们不应将状态压缩看作死板套路，而是应当作为一种设计 DP 状态的手段，做 DP 题的时候，先以正常思路考虑 DP ，而后根据数据范围特点考虑是否使用状态压缩作为设计状态的手段

10.11

T1 图论模型建立，连通块数目 A

T2 贪心，背包问题动态规划 A’

假设已经知道要消灭指定的 $k$ 个怪物以及它们的顺序，那么消耗的生命值为
$$\sum _{i=1}^k(a_i+(i-1)d)(b_i+(i-1)d)$$

现在问题转化为，如何指定这 $k$ 个怪物，如何钦定它们的顺序，考场上我只想出了第二个问题。
先讨论如何钦定它们的顺序：
考虑两个相邻的怪物交换位置，那么其它怪物对猎人生命的消耗不变，只有这两个发生变化，关注交换它们的变化：
$$\begin{array}{rl}& (a_i+(i-1)d)(b_i+(i-1)d)+(a_{i+1}+i\cdot d)(b_{i+1}+i\cdot d)\\ \to & (a_{i+1}+(i-1)d)(b_{i+1}+(i-1)d)+(a_i+i\cdot d)(b_i+i\cdot d)\end{array}$$
展开式子
$$\begin{array}{rl}& a_i{b}_i+(a_i+b_i)(i-1)d+(i-1{)}^2{d}^2+a_{i+1}{b}_{i+1}+(a_{i+1}+b_{i+1})i\cdot d+i^2{d}^2\\ \to & a_{i+1}{b}_{i+1}+(a_{i+1}+b_{i+1})(i-1)d+(i-1{)}^2{d}^2+a_i{b}_i+(a_i+b_i)i\cdot d+i^2{d}^2\end{array}$$
二者作差
$$\Delta =(a_{i+1}+b_{i+1}-(a_i+b_i))d$$

当 $a_{i+1}+b_{i+1}<a_i+b_i$ 时，$\Delta <0$ ，对生命值的消耗减少，所以令 $a_i+b_i$ 大的怪物排在前头最优，这是贪心策略确定顺序。

接下来考虑如何确定这 $k$ 个怪物，我这笨脑子竟然连背包都想不到，吐了…
DP 确定 $k$ 个怪物，问题转化为 01 背包，设 $f(i,j)$ 表示前 $i$ 个怪物中，选 $j$ 个的消耗的最少生命值。

f ( i , j ) = min ⁡ { f ( i , j − 1 ) , f ( i − 1 , j − 1 ) + ( a i + ( j − 1 ) d ) ( b i + ( j − 1 ) d ) } f(i,j)=min{f(i,j-1),f(i-1,j-1)+(a_i+(j-1)d)(b_i+(j-1)d)} f(i,j)=min{f(i,j−1),f(i−1,j−1)+(ai​+(j−1)d)(bi​+(j−1)d)}

接下来输入的猎人的生命值，我们只要在得到的 $f(n,k)$ 中二分就能得知 $k_{\max }$
时间复杂度 $O(N^2+M\log N)$

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ull inf = 99999999999999999;
ull n,m,d,hp;
ull f[3005][3005];

struct monster{
	ull a;
	ull b;
	ull su;
	ull mu;
}mo[3005];

bool cmp(monster x,monster y)
{
	return x.su > y.su;
}

int bisearch(ull x)
{
	int l = 0;int r = n;int mid = 0;int res = 0;
	for(;l <= r;)
	{
		mid = (l + r) >> 1;
		if(f[n][mid] < x)
		{
			res = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	return res;
}

int main()
{
    freopen("hunter.in","r",stdin);
    freopen("hunter.out","w",stdout);
	scanf("%llu%llu%llu",&n,&m,&d);
	for(int i = 1;i <= n;i ++)
		scanf("%llu",&mo[i].a);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%llu",&mo[i].b);
		mo[i].su = mo[i].a + mo[i].b;
		mo[i].mu = mo[i].a * mo[i].b;
	}
	sort(mo + 1,mo + 1 + n,cmp);
	for(int i = 0;i <= n;i ++)
		for(int j = 1;j <= n;j ++)
			f[i][j] = inf;
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= i;j ++)
			f[i][j] = min(f[i][j],min(f[i - 1][j],f[i - 1][j - 1] + (mo[i].a + (ull)(j - 1)*d)*(mo[i].b + (ull)(j - 1)*d)));
	for(int i = 1;i <= m;i ++)
	{
		scanf("%llu",&hp);
		printf("%d ",bisearch(hp));
	}
	return 0;
}

最后

以上就是从容大门为你收集整理的2021十月暂记（1）的全部内容，希望文章能够帮你解决2021十月暂记（1）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。