自助建站营销招商,电商网店怎么做,为什么网站开发成本高,平面广告作品分析Peter推荐算法书#xff1a;《算法导论》 图示#xff1a; 目录
钢条切割
打字怪人 钢条切割
算法导论#xff08;第四版#xff09;第十四章第一节#xff1a;钢条切割
题目描述#xff1a;
给定一根长度为 n 英寸的钢条和一个价格表 #xff0c;其中 i1,2,…,n … Peter推荐算法书《算法导论》 图示 目录
钢条切割
打字怪人 钢条切割
算法导论第四版第十四章第一节钢条切割
题目描述
给定一根长度为 n 英寸的钢条和一个价格表 其中 i1,2,…,n 求切割方案使得总销售价格 最大。如果 足够大最优解可能不需要切割钢条。
这道题可以拆分成两个部分①总价格最大是多少 ②切割方案
先解决①吧。那么我们定义一下f[i]表示长度i的钢条最多能买多少钱。j为切割点。状态转移方程怎么写呢大家先画一张表格理解一下含义。 样例
8
1 5 8 9 10 17 17 20
思考过后是不是特别有灵感所以说状态转移方程如下图所示 原因枚举i,j。当分割点在j时卖的价钱就等于p[j]加上后面的部分的最优值最后再取个最大值即可。 所以①正式解决。②呢我们再定义一个数组fd[i]表示计算f[i]的决策时选择切割多少然后两重循环循环内判断最大fd[i]取值即可代码不告诉了啊应该大家都会写。
打字怪人
题目描述你的儿子小明打字水平有限当他希望打出某个单词如 smart 时他会错误地按到键盘上其他字母例如形成 asnmaaaert 这样的尴尬情况。更加令人崩溃的是小明还不会用退回键或者删除功能来清理错误字母。现在小明从一个词汇表里挑了若干个单词进行打字词汇表里的所有n个单词都已知。请你识别出小明至少打错了几个字符换句话说也就是去掉至少几个字符可以使剩下的内容由词汇表里的真单词拼写出来
做这道题之前先看看另外一道简单题吧。如下
你的儿子小明打字水平有限当他希望打出某个单词如 smart 时他会错误地按到键盘上其他字母键盘例如形成 asnmaaaert 这样的尴尬情况。更加令人崩溃的是小明还不会用退回键或者删除功能来清理错误字母现在请你识别出真正单词每个字母在错误单词中的位置。先输入一行字符串代表小明的打字内容。第二行字符串代表小明真实希望打的单词。小明会确保正确单词所有字母都会依次出现在他打的内容里。
很好大家已经学会了套娃式建模了真不戳。这道题使用双游标会更加游刃有余下面分析控制元素。游标1指向正确单词中的目标字母等待匹配游标2指向打字内容中的字母。那么请大家思考一下哪个游标是主要游标哪个是辅助游标呢当然游标1每次移动一格时游标2可能移动若干格。好了现在代码应该会写了吧。
string a,b;
cinab;
int i0;
for(int j0;jb.size();j){while(ia.size()a[i]!b[j])i;couti ;
}
回到原题。这一题可能需要dp的知识。首先大家思考一下状态怎么定义给出两种选择①f[i]表示前i个字符最少删除几个才能用真实单词拼接② f[i]表示前i个字符最少删除几个才能用真实单词拼接并确保第i个字母必须保留。思考片刻后大家不出意外的话应该都会选①。那么大家真的能快速写出转移方程吗看来我们要找找规律那请大家根据1038题的样例输入填写f[i]。
cinnls;
cins;
for(int i1;in;i) cinw[i];
for(int i1;ils;i){f[i]f[i-1]1;for(int k1;kn;k){lww[k].size();int psearch(i,k);if(p0) continue;f[i]min(f[i],f[p]i-p-lw);}
}
coutf[ls]endl;
请大家思考一下代码的意思。首先第5行是一个提前处理。然后第6行实际上就是在第一层枚举的字符串后再挨个添加真实单词search()是从第i个字母往前查找遇到w[k]起始点时返回相当于前铺
int search(int i,int k){if(ilw) return -1;if(s[i-1]!w[k][lw-1]) return -1;int pai-1;for(int pblw-1;pb0;pb--,pa--){while(pa0s[pa]!w[k][pb]) pa--;if(pa0) return -1;}return pa1;
}
双游标不做解释。
希望这些对大家有用三连必回
