搜索结果
查询Tags标签： DP，共有 1166条记录-
[abc279 G] At Most 2 Colors
G - At Most 2 Colors (atcoder.jp)重点讲解方法三，因为方法三是蒟蒻都能想出来的方法一和方法二都可以借助方法三的思想推出方法一 这是最简单的设置状态的方法，\(dp[i]\)表示前\(i\)个的方案数，然后分类若\([i-k+1,i-1]\)有两种颜色 那么第\(i\)位的取值肯定时这两种…
2023/5/27 1:23:18 人评论 次浏览 -
P3177 树上染色做题记录
树形 dp 好题。 做这题的思想历程： 定义 \(dp_{i,j}\) 表示以 \(i\) 为根的子树中，选择了 \(j\) 个节点的答案。感觉还要带上一维状态就是所有黑点距离 \(i\) 的距离，这违反了做题思路中间的简洁性的原则。于是我们 查看题解。 经过不明方法之后，我们想到了定义 \(dp_…
2022/9/17 23:16:14 人评论 次浏览 -
Codeforces Round #820 (Div. 3) G(字符串 + dp)
Codeforces Round #820 (Div. 3) （字符串 + dp） 题意 两个字符串，一个原串，一个模板串。将原串中所有模板串的最小次数和所有方案数是多少。数据量 \(500\) 思路 考虑对原串中每一个出现的模板串dp。 定义 \(dp[i]\) 表示删除前 \(i\) 个模板串且最后删了 \(i\) 的最小…
2022/9/15 23:18:40 人评论 次浏览 -
I Hate Non-integer Number（DP）
题意 有一个包含\(N\)个元素的数组\(A\). 有\(2^N - 1\)种方式从中选择至少一项。问其中有多少满足平均值为整数。 题目链接：https://atcoder.jp/contests/abc262/tasks/abc262_d 数据范围 \(1 \leq N \leq 100\) 思路 如果选中了\(x_1,x_2,\dots, x_i\)，那么它们的平均…
2022/9/10 6:55:14 人评论 次浏览 -
Problem P12. [算法课动态规划]背包问题
01背包问题，每件物品都有放和不放这两种选择。 使用动态规划思想：有n件物品情况下的总价值最大背包和有n-1件物品情况下的总价值最大背包有关。 我也讲不大明白，对背包问题有兴趣的可以去这看看：https://zhuanlan.zhihu.com/p/93857890#include<iostream> #incl…
2022/9/10 1:24:52 人评论 次浏览 -
优化dp
单调队列优化dp 单调队列单调队列是一种特殊的双端队列，其内部元素具有单调性。常见有最大队列和最小队列两种单调队列，其内部元素分别是单调递减和单调递增的。 支持两种操作 -插入：如果新元素从队尾插入后会破坏其单调性，则删除队尾元素，直到插入后不再破坏单调性为…
2022/9/8 23:53:18 人评论 次浏览 -
remake(DP)---数位dp篇
模板总结 寄搜模板 ll dp[N][state]; // 状态根据题目性质改变, 例子记录数位中 非零 数位的个数 // 从高位向低位递归 ll dfs(int pos, int cnt, bool lead, bool limit){ // (当前数位, 根据题目需要记录状态, 是否有前导零, 前面的数位是否填满)if(pos == -1…
2022/9/7 6:23:07 人评论 次浏览 -
leetcode 45 跳跃游戏 最少次数 C/C++ 动态规划
动态转移方程 dp[pos] = min{dp[pos-k] +1} 当a[pos-k] >= k , k 是两次状态之间a的物理距离。 动态规划并不是这个例子的最好解法，时间复杂度 n^2, 空间复杂度有n, 在 n 比较大时，在有些平台并不能通过。 class Solution { public:int jump(vector<int&g…
2022/9/7 1:37:07 人评论 次浏览 -
Two Permutations (DP搜索的方式) (2022杭电多校3)
题目: 给出长度为 n 的全排列 p , q ，还有一个由 p , q 组成的长度为 2 n 的 S 。现在有一个空序列 R ，每次可以从 p 或 q 的开头取出一个数字并加到 R 的末尾，问有多少种取法使得 R = S , n<=3e5 思路:对于s 的一个位置, 就可能2个位置,来计算贡献, dp[i][j],…
2022/9/6 23:24:22 人评论 次浏览 -
数位dp
数位dp 目录数位dp简介题同类分布\(\text{Balanced Number}\) 简介 数位 \(dp\) 是一种在数位上进行的 \(dp\)，通常用于解决值域 \([L,R]\) 中有几个数满足条件，且 \([L,R]\) 极大 (如 \(1\le L\le R\le 1e18\)) 的问题，这时我们就会在数位上进行 \(dp\)，问题规模变为…
2022/9/5 23:22:59 人评论 次浏览 -
leetcode 674 最长连续递增序列 C/C++ 动态规划，动态规划空间优化，双指针 三种解法，初识动态规划
#if 0 class Solution { //动态规划 public:int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size());int max = 0;for(int i = 0;i< nums.size()-1; i++){if(nums.at(i+1)> nums.at(i)) {dp.at(i+1) = dp.at(i) + 1;}if(dp.at(i+1…
2022/9/5 1:52:48 人评论 次浏览 -
NC24158 [USACO 2015 Jan G]Moovie Mooving
题目链接 题目 题目描述 Bessie is out at the movies. Being mischievous as always, she has decided to hide from Farmer John for L (1 <= L <= 100,000,000) minutes, during which time she wants to watch movies continuously. She has N (1 <= N <…
2022/9/4 6:53:52 人评论 次浏览 -
NC19885 [AHOI2009]CHESS 中国象棋
题目链接 题目 题目描述 在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.一个炮要能攻击另一个炮他们必须要处于同一行或者一列且他们之间有且仅有一个棋子. 输入描述 一行…
2022/9/4 6:22:52 人评论 次浏览 -
cdq分治
cdq分治，一种广为人知的离线分治算法。大体的思想是：将左右两边区间分开递归处理。 统计左边区间修改对右边区间查询的影响。第一步很简单，写两个递归就行了。关键在第二步。我们搞个cdq的经典问题——三维偏序来具体解释这个东西。 P3810 【模板】三维偏序（陌上花开）…
2022/9/3 23:22:59 人评论 次浏览 -
NC20240 [SCOI2005]互不侵犯KING
题目链接 题目 题目描述 在NN的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。 国王能攻击到它上下左右，以及左上 左下右上右下八个方向上附近的各一个格子，共8个格子。 输入描述 只有一行，包含两个数N，K （ 1 ≤ N ≤ 9, 0 ≤ K ≤ N * N） 输出描述 方案…
2022/9/3 6:24:56 人评论 次浏览
