O(mn)O(mn)O(mn)

题目链接1、问题转化若x能变成y，那么就在x和y之间建立一条无向边，边权为1，因此每个x都只会向其约数和y至多建1条边，这符合树的形式，y是x的父亲。所有的x都向各自的y建一条边，最后会构成一个森林（多棵树）。对这些树求树的最大直径就是答案。树的直径2、如何建图要想在x和y之间建一条无向边，就要知道x的约数有哪些。最暴力的做法就是对每个x，枚举其约数1至n\sqrt{n}n​这样的做法是O(nn)

题目链接

题目链接注意题目中的三角形是互不相交的。假设选取如下三角形：由于三角形之间互不相交，所以剩下的三角形只能在[1, 3]、[3, 6]和[6, 1]区间选取。如果我们有[1, 3]和[3, 6]区间三角形顶点积的和的最小值f[1, 3]、f[3, 6]，那我们就能知道区间[1, 6]的最小值f[1, 6] = f[1, 3] + f[3, 6] + w[1] * w[3] * w[6]。接下来假设选

题目链接

题目链接题目关键是如何把不相交问题转化。如果AB和A’B’相交，不妨设A<B，则必有A’>B’，也就是说，A’到B’是下降的如果AB和A’B’不相交，不妨设A<B，则必有A’<B’，也就是说，A’到B’是上升的因此，对ABCD…从小到大排序，同时也把A’B’C’D’按ABCD的顺序排序，寻找A’B’C’D’中最长的上升子序列，序列长度就是答案。#include <io

录一、动态规划1、线性DP2、背包问题3、状态机模型4、状态压缩DP5、区间DP6、树形DP7、数位DP二、搜索

题目链接因为最长上升子序列的f[i]表示以第i位为结尾，最长的序列长度。所以从前到后做一遍最长上升子序列得到f1，从后到前再做一次最长上升子序列得到f2，遍历f1和f2，求f1[i]+f2[i]最大即可。#include <iostream>#include <cstring>using namespace std;int n;int h[1005], f1[1005],

题目链接普通的二维费用背包，费用分别是精灵球数量和皮卡丘体力，相同答案要记下体力最小的。#include <iostream>using namespace std;int n ,m ,k, f[1005][505];int main() {int a, b, c = 0, r = 0;scanf("%d%d%d", &n, &m, &k);for (int i