第八周 算法题解笔记1极值点题目描述
- 给定一个单峰函数f(x)和它的定义域，求它的极值点
- 该单峰函数f(x)保证定义域内有且只有一个极值点，且为极大值点
题解
本题感觉和dp关系不大，主要思路是三分法，和二分法非常类似，但没有二分法常用，主要用途是用来求单峰函数的极值
对于任意一个上凸函数，选取函数上任意两个点A,B（xA<xB），
若满足yA<yB,那么该函数的极值点必然在[xA,+∞)中，
若满足yA>yB，那么该函数极值点必然在(-∞,xB]中，
若满足yA=yB，那么该函数的极值点必然在[xA,xB]中。
对于任意一个下凸函数，选取函数上任意两个点A,B（xA<xB），
若满足yA<yB,那么该函数的极值点必然在(-∞,xB]中，
若满足yA>yB，那么该函数极值点必然在[xA,+∞)中，
若满足yA=yB，那么该函数的极值点必然在[xA,xB]中。
代码
void Solve(){ double left, right, m1, m2, m1_value, m2_value; left = MIN; right = MAX; while (left + EPS = m2_value) right = m2; //假设求解极大值 else left = m1; }}2 硬币问题
https://vjudge.net/problem/洛谷-B3635
题目描述
- 今有面值为 1、5、11 元的硬币各无限枚。
- 想要凑出 n 元，问需要的最少硬币数量。
题解
本题是dp的入门题，和背包问题很像，但硬币问题更简单一些，只需要1维的数组就可以表示
解决dp问题一般需要4步：
确定状态：定义状态，比如
f[i]、f[i][j]代表什么我自己每次做dp的时候都会卡在写状态转移方程那步，后来才发现困难的原因在于第一步定义状态就没有做好，从没深入思考过这样定义状态的原因是什么，自然写状态转移方程就会出错或者写不出来
确定状态往往需要思考两个问题：
- 如何定义最后一步
- 如何划分子问题
写状态转移方程：
当我认真思考上面两个问题之后，状态转移方程就非常容易理解了，根据子问题的问题定义就可以得到
确定初始条件和边界
确定计算顺序
接下来根据这4步分析硬币问题
确定状态
最后一步
假设最后一枚硬币的面值为k，支付n元最少需要的硬币总数可以被表示为：支付n-k元最少需要的硬币数+1（最后一枚）
划分子问题
原问题：支付n元最少需要多少枚硬币
子问题：支付n-k元最少需要多少枚硬币
因此定义状态为f[i]，表示支付i元最少需要f[i]枚硬币
写状态转移方程
每次状态转换都有三种选择，用1元硬币、用5元硬币和用11元硬币
\[f[i]=min\begin{cases}f[i-1]+1& {i\geq 1}\\f[i-5]+1& {i\geq 5}\\f[i-11]+1& {i\geq 11}\end{cases}=min(f[i-1],f[i-5],f[i-11])+1\]
确定初始条件和边界
f[0]=0：0元需要0枚硬币在进行状态转移的时候需要进行判断，需要支付的金额不能比硬币面值小，否则会变成负值
另外由于本题有1元硬币，所以不存在所有硬币都无法支付的情况
确定计算顺序
升序计算，当计算f[i]的时候，需要
f[i-1]、f[i-5]、f[i-11]的值
至此，分析结束，下面是代码
代码
#include#include#includeusing namespace std;int maxn = 10e7;int f[1000005];int main(){ int n; cin>>n; f[0]=0; for(int i=1;i=1){ f[i]=min(f[i], f[i-1]+1); } if(i>=5){ f[i]=min(f[i], f[i-5]+1); } if(i>=11){ f[i]=min(f[i],f[i-11]+1); } } cout<<f[n]<<endl; return 0;}ac截图
3 数塔问题
https://vjudge.net/problem/51Nod-2073
题目描述
有如图所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
题解
为了方便表述，我们默认层数从1开始，而不是0
确定状态
数塔权值表示：
w[i][j]，最后一步
假设数塔共n层，走到最后一层的第j个结点时，最大数字之和可以被表示为：经过左上和右上两条路径的最大数字之和+w[n][j]
划分子问题
原问题：1-n层的最大数字之和
子问题：1-(n-1)层的最大数字之和
因此状态定义为f[i][j]，表示走到第i层第j个结点时的最大数字之和
写状态转移方程
\[f[i][j]=max(f[i-1][j-1],f[i-1][j])+w[i][j]\]
确定初始条件和边界
f[0]=0：0层的数字之和为0对于最左边一列的结点
w[i][0]，只有一个父节点w[i][0]，需要注意判断i-1是否为负数的情况确定计算顺序
升序计算，当计算
f[i][j]的值时，需要f[i-1][j-1]和f[i-1][j]的值
代码
#include#include#includeusing namespace std;int f[105][105];int w[105][105];int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ for(int j=0;j>w[i][j]; } } for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ f[i][j]=0; } } for(int i=1;i<=n;i++){ for(int j=0;j<i;j++){ if(j==0){ f[i][j]=f[i-1][j]+w[i][j]; } else{ f[i][j]=max(f[i-1][j-1],f[i-1][j])+w[i][j]; } } } int ans=0; for(int j=0;j<n;j++){ ans=max(ans,f[n][j]); } cout<<ans<<endl; return 0;}ac截图
4 小美的数组构造
https://www.nowcoder.com/questionTerminal/5ff1c46cc9814c65850bbdabe47e8fbb
题目描述
题目有点长就不复制粘贴了
题解
可以把题目看成总和为m划分成n个数字，且每个数字都和数组a不一样的方案数，可以用dp来解
PS：网上似乎也有差分的思路，之后来学习一下，写在下次笔记里
确定状态
最后一步
假设构造一个数组b，总和为m，长度为n
最后一步应是数组b已经构造了n-1个数字，总和为m-b[n]，b[n]≠a[n]的方案数
划分子问题
原问题：构造长度n总和m且数字和数组a不一样的数组的方案数
子问题：构造长度n-1总和m-b[n]且数字和数组a不一样的子数组的方案数
因此定义状态为f[i][j]，表示前i个数和为j的方案数
写状态转移方程
\[f[i][j]=\Sigma _{k=1}^{j}f[i-1][k]\]
确定初始条件和边界
f[0][0]=1需要注意k≠a[i]，题目要求
确定计算顺序
根据状态转移方程可以看出是升序计算
代码
#include typedef long long ll;using namespace std;ll a[500], f[305][505], m;int mod=1e9+7;int main(){ int n; cin>>n; for(int i=1;i>a[i]; m+=a[i]; } f[0][0]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=1;k<=j;k++) if(k!=a[i]) f[i][j]=(f[i][j]+f[i-1][j-k])%mod; } } cout<<f[n][m]<<endl; return 0;}ac截图
