题意  给定n个物品，每个物品由价值和体积，问装入体积为v的背包的最大价值和恰好装满的最大价值  思路   01背包问题，对于每个物品考虑装和不装即可，如果不装\装不下  ，如果装则考虑装进来后的价值  ，对于每一个物品，在装和不装里取最大即可 。   注意到，n和val最大都可以取1000，二维数组可以开  ,也可以考虑就地滚动进行优化，那么，每次遍历体积时，为了防止重复更新，需要从v遍历到vol[i](倒序遍历)，同时，由于转移只发生在一层数组中，所以每次更新变为和原值比较最大的    初值：对于第一个问题，所有位置初值赋为0即可（可以视作有价值为0体积任意的空气最初填满背包），由于放入每...

题意 给定两个字符串a,b,求a，b最长公共子串 思路  动态规划，最长的子串一定是由倒数第二长的子串加上两个串中一组相同的字符得来的 即：（相同时） （不同）  AC代码 #include<bits/stdc++.h> using namespace std; int f[5050][5050]; int main(){ string a,b; while(cin >> a >> b){ a=' '+a; b=' '+b; if(a[1]==b[1]) f[1][1]=1; for(int i=1;i<a.size();i++){ for(int j...

题意  n个物品，箱子体积为v，装入物品后，箱子的最小剩余体积是多少  思路   动态规划   对于每一个物品，考虑放或者不不放，观察体积   即维护放入前i个物品能否满足体积为j   (当前物品已经比需要的体积大了，放不进去)   (当前物品可以放的进去，考虑放/不放)   特别的，本题有三种写法：正常dp，01滚动，就地滚动   因为每一行的值之和上一行有关，且我们只在乎最后一行的值，每次更新的时候只用看前一行，所以只用两行来存，一行是当前行，一行是上一行，把原来的行号变成mod2意义下的行号即可（01滚动）   由于上一行有的值下一行一定也满足，所以我们可以直接在原有行的基础上改动（就地...

题意  n个人围成环，传球m次，传回第一个人的方案数有多少种？  思路  结束状态为最后一步传回第一个人，上一步为m-1步传回1号左右的两个人  维护即可  AC代码 #include<bits/stdc++.h> using namespace std; int n,m; int dp[50][50]; int main(){ cin >> n >> m; dp[1][0]=1; for(int i=0;i<m;i++){ for(int j=1;j<=n;j++){ if(j==1) dp[j][i+1]+=dp[n][i]+dp[j+1][...

题意  在n*m的地图中，每个点有权值，并且在任一点都可以向四周比自己权值小的点走动，求最多走动多少步  思路  对于走动最长路径的最后一个点，他一定是由上下左右中比他小且已走路径最长的点走来，对于倒数第二个点同理，故需要维护每个点可以走的最长路径，记dp[i][j]为从(i,j)开始走的最长路径，dp[i][j]=max(上下左右权值比他小的值的最长路径+1) 需要注意的是，维护状态转移方程的同时，需要先将每个走到的点最短路径初始化为1，即至少可以走自己这一步，以保证使用记忆化搜索时，走到权值最小的点也能正确维护 本题如果使用递推的话，总需要从地图中权值最小的点开始按升序维护，等价于，可能会...

我竟然有两周没有写过新题解了，也意味着我有两周没怎么看新算法了，近两周实在是很忙，上周六日两天赶去参加团体程序设计天梯赛，ccpc北京市赛，两天都疯狂坐牢，天梯赛离国三线还很远，北京市赛更是全程坐牢，只贡献了一下A和C题思路，敲代码甚至手速都被薄纱，感觉实在是缺少练习。 however，这学期结束之前还是要刷够200个题的，总的来看一天一道多一点就好了，多刷刷吧，总会好起来的

题意  以p(父亲),c(需要挂的最少装饰物个数),t(挂一个装饰物需要的时间)的形式输入每一个树上的节点。 问满足每一个节点的装饰物需求最少需要多少时间  思路  对于叶子节点i，他上面至少悬挂c[i]个装饰物 对于其它节点j，如果他的子节点累计挂的装饰物已经大于等于c[j]，则什么都不用做，如果不够的话，就给总消耗时间加上[c[j]-sum(子树悬挂装饰物总和)]*min(子节点最小悬挂时间)  注意  注意树的建立，用邻接矩阵 注意dfs方式，先递归到头，回溯的时候在判断是否足够  AC代码 #include<bits/stdc++.h> using namespace st...

题意  x*y蛋糕，切成n块等面积的，要求最大块的(长边/短边)最小  思路  对于每一块，切的时候切的位置总为当前块长度或者宽度/当前块要切成的块数，这样才能保证每一块面积相等你 也就是对于(x,y,n)横着切切的一定是x/n的倍数，并且若倍数为i，则一边应该且成i块，另一边应该切成n-i块 于是，每一次枚举横着切还是竖着切，每一种切法中枚举切的倍数i，切成的两份中，去返回值大的（最大边长比），最终在横着切和竖着切的里面小的那个就是更好的 直到n切成1块的时候，直接返回长边/短边的值  AC代码 #include<bits/stdc++.h> using namespace st...

题意  把一个a*b个小正方形组成的大正方形切成两块有多少种切法？  思路  爆搜，对于正方形a*b转化为点阵图坐标为[0,a][0,b] 其中(0,0)(a,0)(0,b)不能作为起点，对于每个起点，找可能的终点即可 由于对称性，两条对边方案重合，所以只搜索一组邻边即可 DFS要从不在边上的点开始，把起点标为访问，所以DFS总是标记了上一个访问的点，进入后要先把当前点标记，同理，回溯也是四个方向尝试完后，把当前点取消标记  #include<bits/stdc++.h> using namespace std; int a,b; long long ans=0; int dir[...

题意  给定k,m,构造一个由0~k-1这些数字组成的数，使得k整除m  思路  利用同余，不断广搜，一个余数出现后，后面再出现相同余数就直接跳过 开始要从1~k的每一个值都试一遍 由于位数很多，需要使用字符串来存储数字  AC代码 #include <bits/stdc++.h> using namespace std; int k, m; bool vis[1007]; struct node { string num; int r; }; string bfs() { queue<node> q; for (int i = 1;i < k;i++) { st...

题意  有n个二元组，每个二元组可以选取一个值，组成一个长为n的序列，问从1开始的最大连通能到几  思路   并查集，对于单一二元组，我们总希望选择其中小的   对于一个连通块：一定属于下述两种情况之一  n个数的连通块，有n-1条边，则最大的元素选不到 n个数的连通块，有超过n-1条边，则所有元素均可选到    所以，读入一个二元组后，总可以把小的元素所属的连通块合并到大的元素所属的连通块之中，同时，把小的元素所属的连通块的父亲标记成可以选取，维护并查集。   特别的，如果两个元素本身就属于一个连通块之中，说明变味了情况二，直接把整个连通块的父亲标为可选   最终，从1开始找第一个没被标记的...

题意  把数字n变为数字m，可以进行如下三种操作：+1，-1，平方，问最少需要几步  思路  bfs每一步的所有可能，记录一个数最早出现的时间 对于步数：最大不会超过n-m步（从n不断+1变为m），同理，如果平方后的数大于等于2m-n，说明减回m的步数一定比从n加到m还多，直接舍去  int solve(int n, int m) { // write code here if(n==m)return 0; int stp[10000]={0}; queue<int>q; q.push(n); while(q.size()){ int now=q.front(); q.pop();...

01BFS  走的时候有两种走法，维护双端队列，一种走法代价是0，进入队首，另一种走法代价是？，放入队尾  题意  给定地图，给定n次起点和终点，每次输出最短时间 特别的，一个点可以向八个方向走，且向其中一个方向走不耗时，其他方向耗时为1  思路  与maze那道题类似，都需要处理队列中时间最短的，但本题不会出现跨越多种不同步长的情况，所以可以不用优先队列，使用一个双端队列来维护即可，对于每一个点尝试移动的时候，不耗时的方向直接放到队首，其余方向放到队尾，仍然保证了队列中耗时差不会超过1秒  AC代码 #include<bits/stdc++.h> using namespace ...

题意  给定蛋糕层数，蛋糕总体积，求解最最小表面积 对于蛋糕每层的半径和高度都是整数，且对于第i层，半径和高度都不小于i  思路  对于每一层，枚举可能的高度和半径，计算体积和表面积 对于枚举顺序，从最底下一层往上枚举，因为上面的层数越多，受限越多 对于每一层，半径和高度的下界都是层数，上界都是上一层的半径-1or高度-1 做到以上，通过20%，其余TLE  剪枝  如果枚举到一定层数，总体积-当前体积已经小于0，直接回溯 如果枚举到一定层数，累计表面积已经大于之前的最优解，直接回溯 如果枚举到一定层数，剩下的体积堆成一块都超过当前最优表面积，直接回溯  对第三条剪枝的论证  对于体积和表面积...