递推

dp入门：从暴力dfs到dp

本篇为小金鱼大佬视频的学习笔记，原视频链接：https://www.bilibili.com/video/BV1r84y1379W?vd_source726e10ea5b787a300ceada715f64b4bf 基础概念暴力dfs很多时候仅能过部分测试点，要想将其优化，一般以 dfs -> 记忆化搜索 …

[bzoj3157][bzoj3516][bzoj4126]国王奇遇记

Description 求∑i1nimmin<10^9,普通版m<200，加强版m<1000，加强版之再加强版m<500000Solution 1.普通版很容易想到倍增的思路，只不过很难实现。设F(n,k)∑ni1ikmi然后,F(n1,k)∑i1n1ikmim∑i2n1ikmim∑i1n(i1)kmi1mm∑i1nm…

codeforces 1529 D.Kavi on Pairing Duty

题面题意给你一个n，坐标上有2n个点，间距为1，让你求出满足题意得方案数。每两个点连接成一条线段，要求线段两两之间要么长度相等，要么一个线段被另一个线段包含题解(找规律) 设ai表示，ni 时有多少方案数…

题目：HDU-2044 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid2044 题目： 一只小蜜蜂... Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 55687 Accepted Submissio…

ZOJ - 3747 Attack on Titans [有条件限制的经典递推计数好题]

题目大意是有n个士兵的排列，士兵有GRP三种类型，要求至少有m个G士兵连续，至多有k个R士兵连续，问有多少种方案，答案取模1e97 题目分析我们看到这个题目，很显然是一个计数的问题，那么如果从简…

杭电ACM——1297，Children’s Queue（递推）

递推公式：f[n]f[n-1]f[n-2]f[n-4]; 突破口：如何得到递推公式，主要是最后一个f[n-4]，这个稍作解释，假如第n,n-1个都是女孩，也就是n-2个人都站好了以后，末尾再插上两个女孩，这个时候&a…

HDU2062,Subset sequence（思维+递推）

emmmmm，题解是看下面的大牛的： https://www.cnblogs.com/AOQNRMGYXLMV/p/3832909.html 简单的说就是，由n个数字构成的所有排列，以1,2,3,…n,为开头的排列的数量是相同的，设为num[n]，因此将m除num[n]就是第一…

杭电ACM--2018（递推）

emmmmmm…一道水题，结果还是弄错了，把递推公式弄错了，结果一直WA。正确题解如下： #include<cstdio> using namespace std; int a[60]; int main() { int n; int i; for(i1;i<59;i) { if(i<4) a[i]i; else a[i]a[i-…

杭电ACM——2085，核反应堆（递推）

突破口： 设i秒高能粒子，低能粒子的数量分别为h[i],l[i]， h[0]1,l[0]0; h[i]3h[i-1]2l[i-1], l[i]h[i-1]l[i-1]. 代码如下： #include<cstdio> #include<iostream> #include<algorithm> #include<cstring>…

codeforces 1472 C Long Jumps 递推

题面题意题解开始想的的是直接模拟题意，遍历一遍然后求最大，TLE，继续优化，可以加记忆化搜索，把遍历过的标记，还是TLE其实是一个递推，直接从后往前遍历即可代码 #include<bits/stdc.h&g…

杭电ACM——2064，汉诺塔III（递推）

突破口：有n个盘子，先将上面n-1个盘子移动最右边，f(n-1)次，再将第n个最下面的盘子移到第二根柱子，再将最右边n-1个移动到最左边，f(n-1)次，再将第n个盘子移到最右边，最后将n-1个盘子又…

AcWing 95. 费解的开关

原题链接：https://www.acwing.com/problem/content/97/看了前几篇题解和y总的视频讲解，总有一个奇怪的点搞不明白，为什么说第一行确定了，第二行就确定了，第三行接下来也就确定了。不做一个假设本蒟蒻怎么会明白(((假设…

灵神笔记(1)----动态规划篇

文章目录介绍动态规划入门：从记忆化搜索到递推打家劫舍递归记忆化递归递推滚动变量背包0-1 背包递归写法记忆化递归目标和记忆化搜索递推两个数组一个数组完全背包记忆化递归搜索零钱兑换记忆化递归递推背包问题变形[至多|恰好|至少] 最长公共子序列记忆化搜索…

递归（recursion）迭代（iteration）

求 n! 有两个思路： 迭代 iteration 递归 recursion //这是递归 int factorial(int n) {if(n>1)reurn n * factorial(n-1);elsereturn 1; }//这是迭代 int factorial(int n) {int i, s1;for(i1; i<n; i){s s * i;}return s; } 递归法就是在运行的过程中调…

AcWing95.费解的开关

题目你玩过“拉灯”游戏吗？25 盏灯排成一个 55 的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其…

leetCode 494. 目标和 + 动态规划 + 记忆化搜索 + 递推 + 空间优化

关于本题我的往期文章： LeetCode 494.目标和 （动态规划性能优化）二维数组压缩成一维数组_呵呵哒(￣▽￣)"的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133253822 给你一个非负整数数组 nums…

【蓝桥杯】翻硬币

翻硬币思路： 其实有点贪心的意思，依次比较，不同就1，然后修改自己的字符串和下一个的字符串，再匹配。 #include<iostream> #include<string> using namespace std;string now,res;int main(void) {cin&g…

Educational Codeforces Round 163 (Rated for Div. 2)（A,B,C,D,E）

比赛链接好忙好忙好忙，慢慢补老比赛的题解了。这场没啥算法，全是思维。有也是BFS，屎。 A. Special Characters 题意： 您将得到一个整数 n n n 。您的任务是构建一串大写的拉丁字母。此字符串中必须正好有 n n n 个特殊字…

HDU 2047 阿牛的EOF牛肉串

题目：HDU-2047 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid2047 题目： 阿牛的EOF牛肉串 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 28348 Accepted Submiss…

AcWing第81 82 83场周赛总结

第81场周赛希望我下次不用再写这种东西这次比赛被国强打爆，希望下次可以有所进步。 T2：等差数列这其实是一个暴力，但是由于参加CSP与NOIp，对于题目的难度想象过高，想的过于复杂，用了个差分的方法&#x…

杭电ACM——2077，汉诺塔IV（递推/思维）

突破口： 既然是汉诺塔，那就非常有可能与原来的汉诺塔问题有联系，手动推出n1,2,3,4的移动次数分别为2,4,10,28，而原汉诺塔问题n1,2,3时分别为2,8,26，有什么发现呢？ 假设原汉诺塔的数列为x1[20]，现…

LeetCode 70.爬楼梯 + 记忆化搜索 + 递推 + 动态规划 + 空间优化

关于此题的我的往期文章： leetCode 70.爬楼梯动态规划_呵呵哒(￣▽￣)"的博客-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133325224?spm1001.2014.3001.5501 上i-1层楼梯，有 dfs(i-1) 种方法&#x…

HDU 2048 神、上帝以及老天爷(递推)

题目：HDU-2048 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid2048 题目： 神、上帝以及老天爷 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 30928 Accepted Su…

SHUOJ 1013 过河卒问题（递推）

题目：SHUOJ 1013 题目链接：http://202.121.199.212/JudgeOnline/problem.php?id1013 题目： 1013: 过河卒 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 1584 Solved: 464 [Submit][Status][Web Board] Description 如图，A…

HDU 2049 不容易系列之(4)——考新郎(错排)(递推)

题目：HDU-2049 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid2049 题目： 不容易系列之(4)——考新郎 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 29663 Accept…

【洛谷】 P1240 诸侯安置（递推）

洛谷P1240 诸侯安置点击此处去OJ 问题描述很久以前，有一个强大的帝国，它的国土成正方形状（需旋转45来看），图1所示为n3时的情况。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，因此国王准备给他们每…

Educational Codeforces Round 57 1096F - Inversion Expectation(递推)

这道题如果用我的方法分解比较多，所以我注释了一下代码，方便大家看_(:з」∠)_. A.问题转化求所有可能的不同序列的逆序数期望. 很容易知道所有不同情况有vac!vac!vac!种,vacvacvac是空位置的个数，这样我们就直接求所有不同序列的逆序数之…

【c++基础】数池塘（四方向）

说明农夫约翰的农场可以表示成N*M（1≤N、M≤100）个方格组成的矩形。由于近日的降雨，在约翰农场上的不同地方形成了池塘。每一个方格或者有积水（W）或者没有积水（.）。农夫约翰打算数出他的农场上…

leetCode 416.分割等和子集 + 01背包 + 动态规划 + 记忆化搜索 + 递推 + 空间优化

关于此题我的往期文章： LeetCode 416.分割等和子集（动态规划【0-1背包问题】采用一维数组dp:滚动数组）_呵呵哒(￣▽￣)"的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133212716看本期文章时&…

LeetCode 0070. 爬楼梯：动态规划（递推）

【LetMeFly】70.爬楼梯：动态规划（递推） 力扣题目链接：https://leetcode.cn/problems/climbing-stairs/ 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#x…

费解的开关

这道题也是一道利用递推的题目，超级有趣首先对于任意一个方块，能改变它的只有它自己，以及它四周的方块因此我们可以这样想，现枚举出第一行的每一种可能性对于第二行的每一个方块来说，只要它上面的方块是亮的&#x…

$AcWing 95. 费解的开关（递推）$