【课程】算法设计与分析——第八周 题解笔记
第八周 算法题解笔记
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 < right){
m1 = left + (right - left)/3;
m2 = right - (right - left)/3;
m1_value = f(m1);
m2_value = f(m2);
if (m1_value >= 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<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int maxn = 10e7;
int f[1000005];
int main()
{
int n;
cin>>n;
f[0]=0;
for(int i=1;i<=n;i++){
f[i] = maxn;
if(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<iostream>
#include<algorithm>
#include<cstring>
using 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<i;j++){
cin>>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 <bits/stdc++.h>
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<=n;i++){
cin>>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截图
