n个节点以1为根的一棵树，每个非叶子节点都有一个操作max或min（0表示min，1表示max），表示这个节点中的值应该分别等于其子节点中所有值的最大值或最小值。假设树上有k个叶节点，你可以将每个叶节点填上[1,k]的数字，且每个数字只使用一次，求根节点的最大值 题解：树形dp 可以看出来是个树形dp结构，f[i]代表i节点下的子树，需要使用多少个节点，即表示节点i的权值在这个子树的所有叶节点中最小排名，那1节点的答案最大就是 k - f[1] + 1 转移： 当前节点如果权值是1，说明要取最大值，那我们就要选一个最小的排名来更新父亲节点，所以对他下面的节点求个min 如果是0，说明要取最小值...

大概意思就是说，每天画一条水平线（若与之前的重合则相当于线的数量不变，每天告诉你画的这条线上的线有多少条）。要每天这条线下的线的数量之和最小，求这个最小值。  题解：首先分析得出要是线下数量最少，因为线上是定值，所以转而求每天线的总数最少。设第i天，线上数为a[i]，线下数为d[i]，线总数为sum[i]。很明显sum[i] = a[i] + d[i] + 1。限制条件：  1.sum[i] ≥ sum[i - 1] 2.sum[i] ≥ a[i] + 1 3.sum[i] ≤ sum[i - 1] + 1 -----> sum[i - 1] >= sum[i] + 1 （因为每天...

题意：点有正权，边有负权。在这样的无根树中找到一条权重最大的链并输出权重(树上最长路径) 题解：将无根树转为有根树，我们把1当做根dp[u]表示节点u开始，子树先得最长路径 转移方程为：dp[u] = max(dp[u], dp[to] + a[u] - edge[i].w)对于每一个子树，找到最长和次长的的路径ans = max(ans, mx1 + mx2 + a[u]) #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 5; const ll i...

题意;长度为n的字符串a, 若a[i]=='s'表示可以放一个简单句.若a[i]=='f'则表示可以放一个循环句 该循环句可以嵌套简单句及循环,并且循环后不能为空句n<=5000 问有多少种意义不同的摆放方式. 题解：这显然是一道DP。 考虑用数组dp[ i ][ j ]来储存状态，即第 i 条语句后放在缩进 j 层的循环内的方案种数，观察可知，当前一条语句为“s”时放在第 j 层循环内的所有方案数都可以放在0j-1层，那么就应该将0j-1的方案数都加上这个值。当前一条语句为“f”时，就往外拓展一层，即放在第 j 层循环内的方案数等于放在第 j-1 层循环内的所有方案数。注意，读入后不能...

题目描述: 给你一个0、1组成的矩阵，大小为 n × m ，你可以把任意的两行的位置相互交换，请你给出变换后能得到的最大子矩阵，满足只由“1”组成。 输入: 第一行给出两个整数 n 和 m (1 ≤ n, m ≤ 5000)。 接下来 n 行每行给出两个给出一个矩阵a，仅有0、1组成，中间没有间隔。 输出: 输出一行一个整数，表示最大子矩阵满足只由“1”组成的大小，无答案输出0。 题解：记录每一行i中的第j个位置能够像右扩多远，然后枚举起点j，对于每一行i，都进行一次最大值判断时间复杂度O(n*m) #include <bits/stdc++.h> using namespace ...

给出一个n个点m条边的有向无环图。问从1到n，在距离不超过k的情况下最多经过多少点，并输出一个方案。 SPFA + dpdp[i][j]表示第i个点经过j条边的最小值 然后二维标记，直接跑SPFA  #include <bits/stdc++.h> using namespace std; const int inf = 1e9 + 9; const int maxn = 1e5 + 5; int head[maxn][2], tot[2]; const int maxm = 5050; int dp[maxm][maxm]; bool vis[maxm][maxm]; int p...

给你一个字符串s ss，每个位置的字符都有一个删除的代价，现在可以删除一定量的字符使得新字符串不包含子串"hard"（可以不连续），求最小代价   #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100005; int n,a[maxn];ll dp[100005][10]; char s[100005]; char t[]="hard"; int main() { scanf("%d",&n); s...

You are given four positive integers x0, x1, a, b. And you know xi=a⋅x(i−1)+b⋅x(i−2) for all i≥2. Given two positive integers n, and MOD, please calculate x_nxn modulo MOD.Does the problem look simple? Surprise! The value of n may have many many digits!输入描述:The input contains two lines.The first lin...

Asterix，Obelix和他们的临时伙伴Suffix、Prefix已经最终找到了和谐寺。然而和谐寺大门紧闭，就连Obelix的运气也没好到能打开它。 不久他们发现了一个字符串S（|S|<=1000000），刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码，于是就大声将字符串朗读了出来，然而并没有什么事发生。于是Asterix又猜想密码一定是字符串S的子串T。 Prefix认为T是S的前缀，Suffix认为T是S的后缀，Obelix却认为T应该是S中的某一部分，也就是说，T既不是S的前缀，也不是S的后缀。 Asterix选择子串T来满足所有伙伴们的想法。同时，在...

题目大意：有n+1个房间。从1-n个房间。每个房间有两扇门。一扇去i+1的房间另一扇去编号为pi的房间。问到达n+1的房间至少要走多少次。如果走过的次数是奇数次：就走pi这个门如果走过的次数是偶数次：就走i+1这个门（初始值1的位置是奇数）dp[i] 表示1到i这个位置需要走多少次门思路：因为 1 <= pi <= i，所以如果你可以向 i+1这个门走过去，则1-i这些门必定全是走过偶数次，当i位置为奇数次时，pi -> i-1这些位置也同样会被重新在走过一次（即所走过的门的数量也同样会再次计算一次）回到原先pi的位置，应为pi继续向p[pi]位置靠近，所以会回到最开始的位置...

给你一个NM的矩阵，其中有白色和黑色两种颜色，我们可以将其中的任意格子颜色变成另外一种颜色，问最少操作多少次（变换颜色），使得这个NM的矩阵变成一个条形码，并且保证相同颜色挨在一起的列数不小于x不大于y、（条形码|||||||） dp[i][0]表示以0为结尾合法的最小染色数dp[i][1]表示以1为结尾合法的最小染色数 #include <bits/stdc++.h> using namespace std; const int maxn = 1005; char str[maxn]; int a[maxn][maxn]; int sum[maxn][2]; int dp[max...

给出 1个长度为 n 的序列，以及 1 个正整数 m。问这个原序列中是否存在非空子序列，使其元素之和能被 m 整除。 把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。代入本题中我们可以发现，当得到这个序列的n个前缀和%m时，一定会出现两个相同的数，这两个前缀和相减得到的序列和一定可以被m整除。因此，当n>m时我们可以特判为序列和一定可以被m整除，从而将n的范围从1e6缩小到1e3 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int a[maxn], vi...

题目大概说有n1个步兵和n2骑兵要排成一排，连续步兵数不能超过k1个，连续骑兵数不能超过k2个，问有几种排列方案。 dp[i][j][x][y]表示已经有i个步兵j个骑兵参与排列且末尾有x个连续步兵或y个连续骑兵的方案数. #include <bits/stdc++.h> using namespace std; const int mod = 100000000; const int maxn = 105; int dp[maxn][maxn][15][15]; int main() { int n1, n2, k1, k2; cin >> n1 >> n...