洛谷P1002 过河卒(动态规划)
题目描述棋盘上 AA 点有一个过河卒,需要走到目标 BB 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示,AA 点 (0, 0)(0,0)、BB 点 (n, m)(n,m),同...
【洛谷】【动态规划/01背包】P1734 最大约数和
【题目描述:】选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。【输入格式:】输入一个正整数S。【输出格式:】输出最大的约数之和。[算法分析:]01背包,每个数的约数和为其价值,数的大小为其花费注意1的价值应该为0[Code:]#include<iostream>...
dp 动态规划 hdu 1003 1087
动态规划就是寻找最优解的过程最重要的是找到关系式hdu 1003题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1003题目大意:求最大字序列和,其实就是分成以0结尾的序列以1结尾的序列以2结尾的序列...以n结尾的序列所以以n结尾的序列的最大值就是以n...
hdu 1176 免费馅饼(动态规划)
AC code:#include<stdio.h>#include<string.h>#define max(a,b) (a>b?a:b)#define maxof3(a,b,c) (max(max(a,b),c))int dp[100005][12];int main...
【暑假】[深入动态规划]UVa 10618 Fixing the Great Wall
UVa 10618 Fixing the Great Wall题目: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36139思路: 数轴上有n个点需要修复,每个点有信息c,x,d 表示位于x且在t时修缮的费用是c+d*t,...
BZOJ_1609_[Usaco2008_Feb]_Eating_Together_麻烦的聚餐_(动态规划,LIS)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=1609给出一串由1,2,3组成的数,求最少需要改动多少个数,使其成为不降或不升序列.分析法1:改动一些数字后变为不升(不降)序列,那么除了需要改动的数字以外,其他的数字本身满足不升(不降),所以求最...
【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,...