一看，要求的是： f[n]=i=1∑n​n! 一看，阶乘，不是可以递推吗？ 但是因为这道题是高精度题，所以反而记忆化搜索相比普通的递推更加好写。 因为n≤50，所以我们需要维护的高精度乘法其实只需要两位数（用于已经得到的阶乘结果与下一项相乘），其实就是高精度乘上低精度的半高精度乘法，不需要正宗的高精度乘法来维护。 所以上手一个半高精度乘法和一个高精度加法（用于维护已经得到的x!和已经得到的f[x−

看成同时从左上开始传两个纸条，用f(i,j,k)表示这一步的横纵坐标之和为i，第一张纸条纵坐标为j，第二张纸条纵坐标为k（因为路径不重合，所以j≠k，不妨令j<k）。可以看出每走一步纸条的横纵坐标之和都会加一，所以i其实就是传递的次数+2. 每个状态可以由以下4种情况转移而来： 第一张纸条由上面，第二张纸条由上面 f(i,j,k)=max{f(i,j,k),f(i-1,j-1,k-1)+a[

经典区间 dp。 首先明确每行怎么取是没关联的，所以可以看成n行每行跑一次区间 dp。对于每行，设fl,r​表示取区间l到r的最大值，这明显从大区间向小区间转移，但这里说一下从小区间向大区间转移。 对于一个区间，它乘的2i的这个i是第i次取数，就应等于区间长度，一个长度为len的区间从len−1转移得到，所以每次转移乘2就可以解决答案乘2i的问题。这里要好好体会。 记ai​表示这一行的第i个数，对

简单枚举题。 思路 n2去枚举每个格子明显是行不通的做法，会喜提超空间。 我们先把每个地毯都存起来，直接考虑筛一遍所有毯子，每次判断有没有覆盖这个点，若覆盖就更新答案即可。 #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e6+5; int a[N],b[N],g[N],k[

思路 用Airport结构体存储机场的x,y坐标，用airports_数组存储所有机场。顺序为先存储第0个城市的4个机场，然后第1个城市的4个机场。。。最后一个城市的4个机场。所以airports_[i]机场所在的城市编号为i / 4。而第i个城市的第j个机场，在airports_中的编号则为i * 4 +ｊ。这两个换算定义成了宏。 输入时通过每个城市的前三个机场坐标计算最后一个机场坐标。 用di

题意 给出一个加法表，一个字母代表一个数字。求加法的进制，以及每个大写字母代表的数字。 数字个数N≤8。（行数≤9） 题解 结论： 一定是N进制。每一行有几个二位数，这个数就是几。 证明： 因为有N个不同的数，所以最少N进制。 假设为N+1进制，那么一定有一个数没有出现，假设为k。 k=0或k=1，而1+N=10，矛盾。1<k≤N，而1+(k−1)=k，矛盾。 其它>N进制的情况同理，

题意 给定一个m×n的矩阵a，要求从(1,1)到(m,n)的最大路径与次大路径之和（只可往下或往右）。 思路 看到题面，马上可以想到 DP。观察数据范围，发现1≤m,n≤50，考虑复杂度为O(n4)的 DP。 我们先来做一做简化版的题面： 给定一个m×n的矩阵a，要求从(1,1)到(m,n)的最大路径（只可往下或往右）。 令fx,y​表示从(1,1)到(x,y)的最大路径。 我们知道，对于每一个(

一道很经典的题目，下面我们来分析下这种问题 这道题显然要先搜索出满足条件的面值组合，比如n=3,k=3时 在搜索时加入适当优化： 以n=3,k=3为例:第一个面值肯定为1，但是第二个面值只能是 但是第二个面值只能是2，3，4，因为面值为1的最多贴3张 贴满的最大值为3，要保证数字连续,那么第二个数字最大是4 所以我们可以得到规律，如果邮票张数为n，种类为k,那么从小到大的顺序，邮票a[i]的下一种

题目大意 有一个n×n的方格图，每个格子都有一个对应的权值ai,j​，你从(1,1)开始走，每次可以从(i,j)走到(i+1,j)或(i,j+1)，最终走到(n,n)，你需要这样走两次，求你所经过的格子上的权值之和的最大值，每个格子上的权值只计算一次。 题目分析 状态：定义一个四维数组f，fijkl​表示第一次走到第i行，第j列，第二次到达第k行，第l列能获得的最大值。 状态转移方程：我们要考虑以

首先有一个最简单的想法：枚举所有的W。 那么此时y可以简单地求出：只需把所有重量小于W的矿石看成不存在（即不算数，也不算价值），对权值和数量各自做前缀和，然后直接按照式子把所有区间的贡献加起来就行了。复杂度O(wi​(n+m))，显然过不了。 进一步优化可以改成只枚举W=wi​的这部分W，因为取两个wi​中间的空当和直接取较大的那个wi​没有什么区别，不会影响重量≥W的矿石的集合。这样做复杂度是O