试题 算法训练 YBH数数

试题 算法训练 YBH数数

问题描述 　　YBH数学很差，她数数时分不清4,5和8；我们定义YBH[i]为YBH的计数法对应的i的值。 　　规定：YBH[4] = 5,YBH[5] = 8；YBH[i]运算规则如下： 　　① YBH[i+j] = YBH[i] + YBH[j] 　　② YBH[ij] = YBH[i] * YBH[j] 　　我们会发现，用不同方法算出的YBH[i]的值是不同的，例如：当i=20时， 　　YBH[20] = 5YBH[4] = 25； 　　YBH[20] = 4*YBH[5] = 32； 　　YBH[20] = YBH[4] * YBH[5] = 40； 　　… 　　我们规定：F[i]为YBH[i]的最大值，现在请你编写一个程序，输入一个数n，输出F[n]的值，若F[n]没有意义，输出-1。

代码：

#include <iostream>
#include <stdio.h>
using namespace std;
int dp[1001];
int jisuan(int num){
          
   
        //先算加法
    int sum=0;
    //从dp[4]一直找到dp[num-4]/2 就能找到加法中的最大值
    for(int i=4;i<=(num-4)/2;i++){
          
   
        if(dp[num-i]==0||dp[i]==0){
          
   //如果dp[x]是0 就说明有一个不存在的值
            continue;
        }
        else{
          
   
            sum=max(sum,dp[i]+dp[num-i]);
        }
    }
    //再算乘法
    int cheng=0;
    //从dp[4]一直找到dp[num/4] 就能找到乘法中的最大值
    for(int i=4;i<=num/4;i++){
          
   
        if(dp[i]!=0&&(num*1.0/i==num/i)){
          
   //判断dp[x]不是不存在 num/i不是小数
            cheng=max(cheng,dp[i]*dp[num/i]);
        }
    }
    return max(sum,cheng);
}
int main(){
          
   
    dp[4]=5;
    dp[5]=8;
    int n;
    cin>>n;
    //从8开始找 因为4和5都知道 6和7都是不存在的，不存在的设为0即可
    for(int i=8;i<=n;i++){
          
   
        dp[i]=jisuan(i);
    }
    /**
    for(int i=4;i<=n;i++){
        printf("%3d:%5d ",i,dp[i]);
        if((i-4)%10==0&&i!=4)
            cout<<endl;
    }
    可以观看输出
    **/
    if(dp[n]==0)
        cout<<-1;
    else
        cout<<dp[n];
    return 0;
}

通过了测试点：