深圳网站建设公司,衣服 div网站,金华网站建设明细报价表,wordpress登陆页面修改今天直接开始讲解FIRST#xff1a;如何抽象出动态规划算法#xff1f;这个问题#xff0c;困扰了无数代OIER#xff0c;包括本蒟蒻在比赛的时候#xff0c;看一道题#xff0c;怎么想到他是什么算法的呢#xff1f;这就需要抽象能力而不同的算法#xff0c;往往有着不同…今天直接开始讲解FIRST如何抽象出动态规划算法这个问题困扰了无数代OIER包括本蒟蒻在比赛的时候看一道题怎么想到他是什么算法的呢这就需要抽象能力而不同的算法往往有着不同的特点就来说说动态规划的题目特点通过遍历能够把所有的情况考虑到。这一点同样适合于递归有可能存在重叠性的子问题。没错这一点也适用于递归有的同学就问了那动态规划和递归不是同样的特点吗回到蒟蒻写的动态规划1里面说过动态规划是可以用递归代替的也就是说如果你的状态转移方程真的实在绞尽脑汁费劲九牛二虎之力也想不出来就用递归来做但代价就是也许拿不到满分SECOND解题思路动态规划抽象出状态之后就要进行遍历每一个状态抽象状态初始化确定循环起始以及边界写出状态转移方程输出return 0;大概就是上述这个过程了每日例题题目描述辰辰是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同的草药采每一株都需要一些时间每一株也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”如果你是辰辰你能完成这个任务吗输入格式第一行有 22 个整数 T1≤≤10001≤T≤1000和 M1≤≤1001≤M≤100用一个空格隔开T 代表总共能够用来采药的时间M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 11 到 100100 之间包括 11 和 100100的整数分别表示采摘某株草药的时间和这株草药的价值。输出格式输出在规定的时间内可以采到的草药的最大总价值。输入输出样例输入 #1复制70 3 71 100 69 1 1 2 输出 #1复制3说明/提示【数据范围】对于 30%30% 的数据≤10M≤10对于全部的数据≤100M≤100。一个纯纯的01背包模板抽象状态f[i]表示第i分钟采到的最大价值初始化no确定循环起始以及边界第一层循环1到m第二层循环t到0真的是01背包模板看不懂的可以借鉴一下上一篇文章写出状态转移方程dp[j]max(dp[j-w[i]]val[i], dp[j]);如果采了这个药那么就要用当前时间减去采药的时间也就是采药之前需要的时间加上现在的状态输出见代码真正做题时大家也可以按照这个顺序非常的清晰那么有的同学就要问了状态定义有什么规律吗首先我们先创建一个数组f数组假设他是一维的然后去想这个一维状态表示什么简单多了就假设是一维尝试写状态转移方程如果发现写不通了也就是有更多的情况表示不出来增加维度然后循环上述操作但是遇到很难的题还得是靠智商因为难的动态规划不仅仅要抽象出来更需要你优化也就是减少维度来迟的AC代码
# include iostream
# include cstdio
using namespace std;
int w[105], val[105];
int dp[1005];
int main(){int t,m; scanf(%d%d,t,m);for(int i1;im;i){scanf(%d%d,w[i],val[i]);}for(int i1;im;i) {for(int jt;j0;j--) {if(jw[i]){dp[j]max(dp[j-w[i]]val[i], dp[j]);}}} printf(%d,dp[t]);return 0;
}这会动态规划系列就真的结束了这次讲算法比之前真的费了更大的力气更多的时间更多的键盘所以希望各位佬能够点个免费的赞如果动态规划方面还有什么不明白的随时私信我我可以出番外篇这篇文章到这里就结束了再见
