【课程】算法设计与分析——第八周 题解笔记

第八周 算法题解笔记

1极值点

题目描述

  • 给定一个单峰函数f(x)和它的定义域,求它的极值点
  • 该单峰函数f(x)保证定义域内有且只有一个极值点,且为极大值点

题解

本题感觉和dp关系不大,主要思路是三分法,和二分法非常类似,但没有二分法常用,主要用途是用来求单峰函数的极值

  1. 对于任意一个上凸函数,选取函数上任意两个点A,B(xA<xB),

    若满足yA<yB,那么该函数的极值点必然在[xA,+∞)中,

    若满足yA>yB,那么该函数极值点必然在(-∞,xB]中,

    若满足yA=yB,那么该函数的极值点必然在[xA,xB]中。

  2. 对于任意一个下凸函数,选取函数上任意两个点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步:

  1. 确定状态:定义状态,比如f[i]f[i][j] 代表什么

    我自己每次做dp的时候都会卡在写状态转移方程那步,后来才发现困难的原因在于第一步定义状态就没有做好,从没深入思考过这样定义状态的原因是什么,自然写状态转移方程就会出错或者写不出来

    确定状态往往需要思考两个问题:

    • 如何定义最后一步
    • 如何划分子问题
  2. 写状态转移方程:

    当我认真思考上面两个问题之后,状态转移方程就非常容易理解了,根据子问题的问题定义就可以得到

  3. 确定初始条件和边界

  4. 确定计算顺序

接下来根据这4步分析硬币问题

  1. 确定状态

    • 最后一步

      假设最后一枚硬币的面值为k,支付n元最少需要的硬币总数可以被表示为:支付n-k元最少需要的硬币数+1(最后一枚)

    • 划分子问题

      原问题:支付n元最少需要多少枚硬币

      子问题:支付n-k元最少需要多少枚硬币
      因此定义状态为f[i] ,表示支付i元最少需要f[i]枚硬币

  2. 写状态转移方程

    每次状态转换都有三种选择,用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 \]
  3. 确定初始条件和边界

    f[0]=0 :0元需要0枚硬币

    在进行状态转移的时候需要进行判断,需要支付的金额不能比硬币面值小,否则会变成负值

    另外由于本题有1元硬币,所以不存在所有硬币都无法支付的情况

  4. 确定计算顺序

    升序计算,当计算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

  1. 确定状态

    数塔权值表示:w[i][j]

    • 最后一步

      假设数塔共n层,走到最后一层的第j个结点时,最大数字之和可以被表示为:经过左上和右上两条路径的最大数字之和+w[n][j]

    • 划分子问题

      原问题:1-n层的最大数字之和

      子问题:1-(n-1)层的最大数字之和
      因此状态定义为f[i][j],表示走到第i层第j个结点时的最大数字之和

  2. 写状态转移方程

    \[ f[i][j]=max(f[i-1][j-1],f[i-1][j])+w[i][j] \]
  3. 确定初始条件和边界

    f[0]=0:0层的数字之和为0

    对于最左边一列的结点w[i][0],只有一个父节点w[i][0],需要注意判断i-1是否为负数的情况

  4. 确定计算顺序

    升序计算,当计算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:网上似乎也有差分的思路,之后来学习一下,写在下次笔记里

  1. 确定状态

    • 最后一步

      假设构造一个数组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的方案数

  2. 写状态转移方程

    \[ f[i][j]=\Sigma _{k=1}^{j}f[i-1][k] \]
  3. 确定初始条件和边界

    f[0][0]=1

    需要注意k≠a[i],题目要求

  4. 确定计算顺序

    根据状态转移方程可以看出是升序计算

代码

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

热门相关:苍穹龙骑   至尊龙帝陆鸣   你好,墨先生   黜龙   至尊龙帝陆鸣