网站建设公司招聘面试,大气公司网站源码,小蓝网页浏览器,网络直播营销方式文章目录 一、简单数学问题习题练习 1、1 买不到的数目 1、1、1 题目描述 1、1、2 题解关键思路与解答 1、2 饮料换购 1、2、1 题目描述 1、2、2 题解关键思路与解答 二、DP问题习题练习 2、1 背包问题 2、1、1 题目描述 2、1、2 题解关键思路与解答 2、2 摘花生 2、2、1 题目… 文章目录 一、简单数学问题习题练习 1、1 买不到的数目 1、1、1 题目描述 1、1、2 题解关键思路与解答 1、2 饮料换购 1、2、1 题目描述 1、2、2 题解关键思路与解答 二、DP问题习题练习 2、1 背包问题 2、1、1 题目描述 2、1、2 题解关键思路与解答 2、2 摘花生 2、2、1 题目描述 2、2、2 题解关键思路与解答 2、3 最长上升子序列 2、3、1 题目描述 2、3、2 题解关键思路和解答 三、总结 标题蓝桥杯——数学与简单DP问题习题练习 作者Ggggggtm 寄语与其忙着诉苦不如低头赶路奋路前行终将遇到一番好风景 一、简单数学问题习题练习 蓝桥杯比赛中常见的还有一类数学问题这些数学问题有的是有公式计算有的是考察的思维逻辑。我们具体来看例题。 1、1 买不到的数目
1、1、1 题目描述 题目来源第四届蓝桥杯省赛CA组,第四届蓝桥杯省赛JAVAC组 题目难度简单 题目描述小明开了一家糖果店。他别出心裁把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候他就用这两种包装来组合。当然有些糖果数目是无法组合出来的比如要买 10 颗糖。你可以用计算机测试一下在这种包装情况下最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。本题的要求就是在已知两个包装的数量时求最大不能组合出的数字。 输入格式 两个正整数 n,m表示每种包装中糖的颗数。 输出格式 一个正整数表示最大不能买到的糖数。 数据范围 2≤n,m≤1000 保证数据一定有解。 输入样例 4 7输出样例 17 1、1、2 题解关键思路与解答 我们先关插题目是两个数找到这两个数最大凑不出来的数。当两个数是由除1外还有其他的公约数时我们发现并不能找到这两个数最大凑不出来的数。也就是当两个数互质时才能够找出这两个数最大凑不出来的数。这里是有一个公式的我们假设这两个数分别是p、q两个数互质那么求这两个数最大凑不出来的数的公式为p-1*q-1-1。我们看一下本题的代码。 #includeiostreamusing namespace std;int p,q;int main()
{cinpq;cout(p-1)*(q-1)-1;return 0;
}
1、2 饮料换购
1、2、1 题目描述 题目来源第六届蓝桥杯省赛CA/C组,第六届蓝桥杯省赛JAVAB组 题目难度简单 题目描述乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料凭3个瓶盖可以再换一瓶C型饮料并且可以一直循环下去(但不允许暂借或赊账)。请你计算一下如果小明不浪费瓶盖尽量地参加活动那么对于他初始买入的 n 瓶饮料最后他一共能喝到多少瓶饮料。 输入格式 输入一个整数 n,表示初始买入的饮料数量。 输出格式 输出一个整数表示一共能够喝到的饮料数量。 数据范围 0n10000。 输入样例 100输出样例 149 1、2、2 题解关键思路与解答 本题目主要考察的是思维逻辑能力。我们要注意的是本题有一个陷阱就是我们需要注意用瓶盖换瓶子的时候可能会有剩余下次再换的时候我们的瓶盖数量就是已经换购的饮料数量加喝完上上次剩下的瓶盖数量。我们直接看代码。 #includeiostreamusing namespace std;int n;int main()
{cinn;int sumn;int retn;while(ret 3){sumret/3;retret/3ret%3;}cout sum;return 0;
}
二、DP问题习题练习
2、1 背包问题
2、1、1 题目描述 题目来源AcWing 题目难度简单 题目描述有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi价值是 wi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。 输入格式 第一行两个整数NV用空格隔开分别表示物品数量和背包容积。 接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数表示最大价值。 数据范围 0N,V≤1000 0vi,wi≤1000。 输入样例 4 5
1 2
2 4
3 4
4 5输出样例 8 2、1、2 题解关键思路与解答 这里我们用闫氏DP分析法进行分析 上述思想的关键就是状态计算。我们不选第 i 个物品时其前 i-1个物品的总价值和为 f[i-1][j]那么第 i 个物品的价值也为 f[i-1][j]。如我们选上第 i 个物品时计算其价值为前 i-1 个物品的价值表示为 f[i-1][j-v[i]]那么选上第i个物品的价值为 f[i-1][j-v[i]] w[i]。在两者值减去一个较大的就行。我们看代码的实现。 #includeiostream
#includecstring
#includealgorithmusing namespace std;const int N 1010;int f[N][N];int n,m;int v[N],w[N];
int main()
{cinnm;for(int i1;in;i)cinv[i]w[i];for(int i1;in;i){for(int j0;jm;j){f[i][j]f[i-1][j];if(jv[i])f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);}}coutf[n][m]endl;return 0;
}
2、2 摘花生
2、2、1 题目描述 题目来源《信息学奥赛一本通》 题目难度简单 题目描述Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图)从西北角进去东南角出来。地里每个道路的交叉点上都有种着一株花生苗上面有若干颗花生经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走不能向西或向北走。问Hello Kitty最多能够摘到多少颗花生。 输入格式 第一行是一个整数T代表一共有多少组数据。 接下来是T组数据。 每组数据的第一行是两个整数分别代表花生苗的行数R和列数 C。 每组数据的接下来R行数据从北向南依次描述每行花生苗的情况。每行数据有C个整数按从西向东的顺序描述了该行每株花生苗上的花生数目M。 输出格式 对每组输入数据输出一行内容为Hello Kitty能摘到得最多的花生颗数。 数据范围 1≤T≤100, 1≤R,C≤100, 0≤M≤1000。 输入样例 2
2 2
1 1
3 4
2 3
2 3 4
1 6 5输出样例 8
162、2、2 题解关键思路与解答 该题我们同样用闫氏DP分析法 状态计算中的集合划分大部分情况下的依据是最后不相同的一步。这道题就是走到右下角只能是从正上走过来或者正左走过来。我们只需要选出这两者的较大的一个再加上右下角的花生数量即可。我们结合着代码一起理解一下。 #includeiostreamusing namespace std;const int N110;int f[N][N],w[N][N];int n,m;int main()
{int T0;cinT;while(T--){cinnm;for(int i1;in;i){for(int j1;jm;j){scanf(%d,w[i][j]);}}for(int i1;in;i){for(int j1;jm;j){f[i][j]max(f[i-1][j],f[i][j-1])w[i][j];}}coutf[n][m]endl;}return 0;
}2、3 最长上升子序列
2、3、1 题目描述 题目来源AcWing 题目难度简单 题目描述给定一个长度为 N 的数列求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数 N。 第二行包含 N 个整数表示完整序列。 输出格式 输出一个整数表示最大长度。 数据范围 1≤N≤1000 −1e9≤数列中的数≤1e9。 输入样例 7
3 1 2 1 8 5 6输出样例 4 2、3、2 题解关键思路和解答 该题目可能会给很多同学造成一个错误的理解。题目中的要求是求数值严格单调递增的子序列的长度最长是多少指的是不是连续的也行。如上述案例最大上升子序列为1256。那该怎么求呢我们用闫氏DP法进行分析 这里关键的就是我们枚举出以i结尾的最大的长度即可。最后在从不同结尾当中找出最大值。那我们怎么计算出以i结尾的最大长度呢我们只需要在i之前且比 a[i] 的就行更新 f[i] 的值即可。我们结合着代码一起理解一下 #includeiostreamusing namespace std;const int N1010;int a[N],f[N];int main()
{int n;cinn;for(int i1;in;i)cina[i];for(int i1;in;i){f[i]1;for(int j1;ji;j){if(a[j]a[i])f[i]max(f[i],f[j]1);}}int res0;for(int i1;in;i)resmax(res,f[i]);coutres;return 0;
} 三、总结 关于数学的问题我们主要是对刷题进行练习巩固。DP动态规划的问题大多数情况是有固定的分析路线也是需要多加做题练习。 今天的练习就到这里希望以上内容对你有所帮助感谢观看。
