题意：给一个树形图(有向树)，n个节点，n-1条有向边，要求选一个节点作为根，使需要改变方向的边的数目最少。并输出所有可能作为根的点。 设dp[i]表示以i为根，需要改变多少个边方向 题解：首先dfs从下向上dp[i],然后在dfs一次从上更新dp[i] #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int head[maxn], tot, dp[maxn]; const int inf = 1e9; int mm = inf; struct Edge { int u, v, opt,...

给你k个长度为n的排列，求这些排列的最长公共子序列的长度 题解：k个都是一个排列，所以，每一个数在自己的的排列中只会出现一次，所以，我们可以记录每一个数在k个排列中的位置，然后就变成了k维偏序问题，a[i] <= a[j]  #include <bits/stdc++.h> using namespace std; const int maxn = 1005; struct node { vector<int> vec; }a[maxn]; int dp[maxn]; bool cmp(node a, node b) { return a.vec[0] < ...

题意：你面前有宽度为1，高度给定的连续木板，每次可以刷一横排或一竖列，问你至少需要刷几次。 思路：先逆推，dp[i][j]表示第i列以后的木板都刷完了（不包括第i列）且前面的第j列是横着刷的（且假设它能够刷到后面的第i+1列），那么第i列之后不包括第i列最少需要的次数。所以当value[j]>=value[i]的时候第i列就不用刷了。 尽管这种做***出现一些不合法的情况，但是最后的推出的结果运用到的必然都是合法的情况。 我们再正着看。 最后的答案应该是dp[0][0]，因为第0列是横着刷的就相当于没刷，第0列以后的都刷完了，就相当于刷完所有的。 它的来源是min(dp[1][0]+1,...

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。 输入格式输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。 输出格式仅一行，包含一个数，即最少的涂色次数。 输入输出样例输入 #1复制 AAAAA输出 #1复制 1输入 ...