【Luogu1291】百事世界杯之旅（动态规划，数学期望）
【Luogu1291】百事世界杯之旅（动态规划，数学期望）题面洛谷题解设\(f[i]\)表示已经集齐了\(i\)个名字的期望现在有两种方法：先说我自己的：\[f[i]=f[i-1]+1+(1-p)(1*p^1+2*p^2+....)\]其中\(p=\frac{i-1}{n}\)为什么，很简单首先要多...
九度OJ 1531 货币面值(网易游戏2013年校园招聘笔试题) -- 动态规划
题目地址：http://ac.jobdu.com/problem.php?pid=1531题目描述： 小虎是游戏中的一个国王，在他管理的国家中发行了很多不同面额的纸币，用这些纸币进行任意的组合可以在游戏中购买各种装备来提升自己。有一天，他突然很想知道这些纸币的组合不能表示的最小面额是多少，请聪明的你...
动态规划VS分治策略
•在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。•动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，而我们能够保存已经解决的子问题的答案，在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表...
九度OJ 1042 Coincidence -- 动态规划（最长公共子序列）
题目地址：http://ac.jobdu.com/problem.php?pid=1042题目描述： Find a longest common subsequence of two strings.输入： First and second line of each input case conta...
动态规划——B 最大高度问题
B - LISTime Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uSubmit StatusDescription一组研究人员正在设计一项实验，以测试猴子的智商。他们将挂香蕉在建筑物的屋顶，同...
动态规划（区间DP）：HDU 5115 Dire Wolf
Dire wolves, also known as Dark wolves, are extraordinarily large and powerful wolves. Many, if not all, Dire Wolves appear to originate from Draenor....
[LeetCode] Longest Valid Parentheses 动态规划
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.For "(()", the lon...
【BZOJ1304】[CQOI2009]叶子的染色（动态规划）
【BZOJ1304】[CQOI2009]叶子的染色（动态规划）题面BZOJ洛谷题解很简单。设\(f[i][0/1/2]\)表示以\(i\)为根的子树中，还有颜色为\(0/1/2\)（\(2\)就是没有染色）的叶子节点的路径上没有任何一个染色的点。随便转移一下就好了。#include<iostr...
[openjudge-动态规划]买书
题目描述描述小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。问小明有多少种买书方案？（每种书可购买多本）输入一个整数 n，代表总共钱数。（0 <= n <= 1000）输出一个整数，代表选择方案种数样例输入样例输入1：20样例输入2：15样例输入3：0样例输出样...
【BZOJ3530】数数（AC自动机，动态规划）
【BZOJ3530】数数（AC自动机，动态规划）题面BZOJ题解很套路的\(AC\)自动机+\(DP\)首先，如果长度小于\(N\)就不存在任何限制直接大力\(DP\)然后强制限制不能走到带有标记的点上面如果长度恰好为\(N\)的长度那么，要考虑是否恰好卡在范围里面于是\(DP\)状态多记一维表示是...
UVA10534-----Wavio Sequence-----动态规划之LIS
题目地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1475题目意思：给你一个序列，告诉你Wavio序列的定义若一个Wavio序...
【WC2001】【cogs358】高性能计算机（动态规划）
【WC2001】【cogs358】高性能计算机（动态规划）##题面【问题描述】现在有一项时间紧迫的工程计算任务要交给你——国家高性能并行计算机的主管工程师——来完成。为了尽可能充分发挥并行计算机的优势，我们的计算任务应当划分成若干个小的子任务。这项大型计算任务包括A和B两个互不相关的较小的计算任务。...
51 Nod 1354 选数字（体现动态规划的本质）
1354 选数字 基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题 收藏 关注当给定一个序列a[0],a[1],a[2],...,a[n-1] 和一个整数K时，我们想找出,有多少子序列满足这么一个条件：把当前子序列里面的所有元素乘起来恰好等于K。样例解释：对于第一个...
Leetcode 121. Best Time to Buy and Sell Stock 最佳股票售卖时(动态规划，数组，模拟)
题目描述已知一个数组，第i个元素表示第i天股票的价格，你只能进行一次交易（买卖各一次），设计算法找出最大收益测试样例Input: [7, 1, 5, 3, 6, 4]Output: 5最大收益 = 6-1 = 5 (不是7-1 = 6,因为先买后卖，7买，1买亏了6)Input: [7, 6, 4,...
洛谷P1002 过河卒 [2017年4月计划 动态规划15]
P1002 过河卒题目描述棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过20的整数)，同样...
洛谷P1002 过河卒 题解 动态规划
题目链接：https://www.luogu.com.cn/problem/P1002题目大意棋盘上\(A\)点有一个过河卒，需要走到目标\(B\)点。卒行走的规则：可以向下、或者向右。同时在棋盘上CC点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。...
POJ 2151 Check the difficulty of problems （动态规划-可能DP）
Check the difficulty of problemsTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 4522 Accepted: 1993DescriptionOrganizing a programming conte...
BZOJ_4197_[Noi2015]寿司晚宴_状态压缩动态规划
BZOJ_4197_[Noi2015]寿司晚宴_状态压缩动态规划Description为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。在晚宴上,主办方为大家提供了 n−1 种不同的寿司，编号 1,2,3,…,n−1，其...
BZOJ_1778_[Usaco2010_Hol]_Dotp_驱逐猪猡_(期望动态规划+高斯消元+矩阵)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=1778炸弹从1出发,有\(\frac{P}{Q}\)的概率爆炸,如果不爆炸,等概率移动到连通的点.求在每个点爆炸的概率.分析我们构造一个\(n\)行\(n\)列的矩阵\(f\),其中\(f[i][j...
【LOJ#575】【LNR#2】不等关系（容斥，动态规划，分治FFT）
【LOJ#575】【LNR#2】不等关系（容斥，动态规划，分治FFT）题面LOJ题解一个暴力\(dp\)，设\(f[i][j]\)表示考虑完了前\(i\)个位置，其中最后一个数在前面所有数中排名是第\(j\)大，那么转移的时候枚举一下当前数是第几大，并且满足不等式的限制就可以了，然后拿前缀和优化一下...