解题思路 这是一个贪心算法题目。为了使保留下来的数字最大，我们需要：   从左往右遍历数字，每次删除一个数字时：  找到第一个比后面数字小的位置 删除该位置的数字 这样可以保证剩余数字最大    重复上述过程  次，直到删除够指定数量的数字   代码   c++   java   python   #include <iostream> #include <string> using namespace std; int main() { string number; int cnt; cin >> number >> cnt; string r...

解题思路 这是一道动态规划优化的题目。关键优化点在于对状态空间的压缩：   直接DP会超时：  如果直接定义  为到达第  点的最小石子数 由于  可达 ，复杂度将达到 ，显然超时    状态空间优化：  观察到石子数  最多只有  个 两个石子间距离如果大于 ，中间的点可以压缩 对于距离大于  的情况，只需保留  的长度    动态规划设计：   表示到达压缩后第  个位置需要的最小石子数 转移方程：，  数组标记压缩后的位置是否有石子    代码   c++   java   python   #include <cstdio> #include <algorithm&g...

版本一：（python存在超时） 解题思路 这是一个区间DP问题，使用四维状态来解决：   状态定义：   表示  串区间  和  串区间  能否组成回文串  是  串的左右边界， 是  串的左右边界    状态转移：  当长度为1时， 对于  串内部：如果 ，则可以从  转移 对于  串内部：如果 ，则可以从  转移 对于 、 串之间：  如果 ，则可以从  转移 如果 ，则可以从  转移      答案：  遍历所有可能的区间组合，找到能形成回文串的最大长度    代码   c++   java   python   #include <iostream> #include &...

解题思路 对于大范围  内的数字统计，需要使用数位DP的方法：   将问题转化为求 ，表示  到  中每个数字出现的次数  则区间  的答案为     对于计算 ：  考虑每一位的贡献 例如对于数字 ：  个位：每  个数， 各出现  次 十位：每  个数，每个数字在十位上出现  次 百位：每  个数，每个数字在百位上出现  次 千位： 出现  次， 出现  次， 出现  次      核心思路：  对每一位，计算该位上的每个数字出现次数 需要考虑当前位是否受限    代码   c++   java   python   #include <iostream> #include &...

解题思路 本题要求计算长度不超过  且包含子序列 "us" 的小写字母字符串数量。可以使用动态规划解决：   状态定义：   表示长度为  时的状态  : 还未出现  : 已经出现 ，还未出现  : 已经出现     状态转移：   // 前一个状态未出现 ，新字母不是   // 新字母是  或 新字母不是   // 新字母是  或 新字母任意    初始状态：   // 除了  的所有字母  // 只有   // 不可能出现     最终结果：所有长度的  之和   代码   c++   java   python   #include <iostream> ...

解题思路   核心思想：  将数字转为字符串，计算所有数位之和  如果能找到一些数位，使其和为 ，则可以实现要求 本质是一个子集和问题    解决方案：  先判断总和是否为偶数（如果为奇数则无解） 使用状态压缩DP或DFS判断是否存在子集和为  由于数据范围较小（最多18位数字），可以直接DFS    代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; bool can_split(string& num, int target) { int n = num.length(); v...

解题思路   核心思想：  使用状态压缩DP解决，状态表示为 ，其中  表示当前点， 表示已访问点集合  表示当前在点 ，已经访问了  表示的点集合时的最小花费 通过二进制表示已访问的点集合    状态转移：  对于当前状态 ，枚举下一个要访问的点      代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; const int N = 205; const int M = 16; const int INF = 0x3f3f3f3f; int n, m, R; int dist[N][N...

解题思路   核心思想：  对于每个节点，有两种状态：选择或不选择 如果选择当前节点，则不能选择其子节点 如果不选择当前节点，则可以选择或不选择其子节点    状态定义：   表示不选择节点  时的最大金额  表示选择节点  时的最大金额    状态转移：   对所有子节点   对所有子节点     代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; const int N = 100010; vector<int> children[N]; int values[N]; in...

解题思路   核心思想：  对于每个节点，需要考虑经过该节点的最大路径和 路径可以是：左子树->节点->右子树，或者左子树->节点，或者右子树->节点 需要自底向上计算，使用DFS    关键点：  每个节点需要返回：从该节点出发的最大路径和（只能选择一个子树） 同时需要更新全局最大路径和（可以包含两个子树） 注意处理负数情况    代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; const int N = 100010; vector<int> c...

解题思路   核心思想：  使用DFS预处理每个节点的子树中红色节点数量 对于每次查询直接返回预处理的结果    实现步骤：  根据父节点数组构建树（邻接表） DFS遍历树，统计每个节点子树中的红色节点数 处理查询    代码   cpp   java   python   #include <bits/stdc++.h> using namespace std; const int N = 100010; vector<int> g[N]; // 邻接表 int count_red[N]; // 每个节点子树中的红色节点数 string colors; // 节点颜色...

解题思路   核心思想：  使用  数组标记配对关系： 表示节点  和  需要染成相同颜色 通过两次DFS完成配对和染色    第一次DFS (dfs1)：确定配对关系  从根节点开始，自底向上处理 对于叶子节点或未配对的节点：  如果其父节点已配对，则无解 否则，将该节点与其父节点配对（赋予相同的  值）   配对号  从  开始递增    第二次DFS (dfs2)：根据配对关系染色  从根节点开始，自顶向下染色 如果两个节点配对号相同，则染相同颜色 如果配对号不同，则染相反颜色    代码   c++   java   python   #include <bits/stdc++....

解题思路   这是一个树形DP问题：   表示不选择节点  时，以  为根的子树能访问的最大天数  表示选择节点  时，以  为根的子树能访问的最大天数    状态转移：  当选择  时 ()：必须选择所有子节点的不选择状态 () 当不选择  时 ()：每个子节点可以选择或不选择，取     边界条件：  选择当前节点时，天数+1 ()    代码   c++   java   python   #include<bits/stdc++.h> using namespace std; const int MAX_N = 500005; int n, s; int f[MAX_N][...

解题思路   状态定义：   表示当前剩余区间  能获得的最大价值 当前是第  次取数    转移方程：    边界条件：   时，    代码   c++   java   python   #include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int A[MAXN], B[MAXN]; long long dp[MAXN][MAXN]; int main() { int n; cin >> n; // 读入数列A和B for(int i = 0; i < n; i++) cin...

解题思路   状态定义：   表示使区间  的括号序列合法所需插入的最少括号数    转移方程：  当  和  匹配时： 否则：    代码   c++   java   python   #include <bits/stdc++.h> using namespace std; int dp[105][105]; bool match(char left, char right) { return (left == '(' && right == ')') || (left == '[' && right == ']'); } int main()...