【课程】算法设计与分析——第八周题解笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了【课程】算法设计与分析——第八周题解笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第八周算法题解笔记

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截图

【课程】算法设计与分析——第八周题解笔记文章来源地址https://www.toymoban.com/news/detail-746190.html