问题描述
YBH数学很差，她数数时分不清4,5和8；我们定义YBH[i]为YBH的计数法对应的i的值。
规定：YBH[4] = 5,YBH[5] = 8；YBH[i]运算规则如下：
① YBH[i+j] = YBH[i] + YBH[j]
② YBH[i*j] = YBH[i] * YBH[j]
我们会发现，用不同方法算出的YBH[i]的值是不同的，例如：当i=20时，
YBH[20] = 5*YBH[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。
输入格式
一个数n(8 <= n <= 1000)
输出格式
输出F[n]的值.
样例输入
20
样例输出
40
样例输入
11
样例输出
-1
数据规模和约定：
8 <= n <= 1000
思路：
从题目中几个公式我们可以看出使用动态规划来解决，它的公式类似状态转移方程，题中也给出了初态：dp[4]=5,dp[5]=8，所以重要的就是找到状态转移方程。
对于i状态dp[i]，可以是dp[i-4]、dp[i-5]或者dp[m]*dp[n]（m和n都是 i 的因数且m*n= i）转移过来的，所以dp[i]为dp[i-4],dp[i-5]和dp[m]*dp[n]的最大值。
初始化：
int n = new Scanner(System.in).nextInt(); int[] dp = new int[n+1];//新建dp数组 Arrays.fill(dp, -1); //让所有值都为-1 dp[4] = 5; dp[5] = 8; //初态
第一和第二种情况的较大值好判断：
for (int i = 8; i <= n; i++) {
if (dp[i-4]!=-1) //先直接让dp[i]从dp[i-4]转移过来
dp[i] = dp[i-4] + 5;
if (dp[i-5]!=-1)
dp[i] = Math.max(dp[i], dp[i-5] + 8);//再看从dp[i-5]转移过来是否更优
findMult(dp,i); //最后看从dp[m]*dp[n]的情况下转移过来是否更优
}
第三种情况dp[m]*dp[n]，我们要去找到 i 的所有因数，看它所有情况的最大值，所以我用了一个函数findMult()去更新最大值：
public static void findMult(int[] dp, int m) {
List list = getYinsu(m); //获取m的因数
for (int k : list) {
if(dp[k]!=-1&&dp[m/k]!=-1) //两个数都要不为-1时才修改
//这里m/k一定为整数，因为k是m的因数
dp[m] = Math.max(dp[m], dp[k]*dp[m/k]);//判断更新较大值
}
}
getYinsu()方法用来找因数：
i * i <= num就结束可以减少计算量，例如4 * 9 = 9 * 4，即dp[4] * dp[9] = dp[9] *dp[4]，
public static ListgetYinsu(int num) { List list = new ArrayList<>(); //直接让因数从4开始，因为从dp[4]才开始有值 for (int i = 4; i*i <= num; i++) { if (num%i==0)//能整除就加入 list.add(i); } return list; }
完整代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n = new Scanner(System.in).nextInt();
int[] dp = new int[n+1];
Arrays.fill(dp, -1); //让所有值都为-1
dp[4] = 5; dp[5] = 8; //初态
for (int i = 8; i <= n; i++) {
if (dp[i-4]!=-1) //先直接让dp[i]从dp[i-4]转移过来
dp[i] = dp[i-4] + 5;
if (dp[i-5]!=-1)
dp[i] = Math.max(dp[i], dp[i-5] + 8);//再看从dp[i-5]转移过来是否更优
findMult(dp,i); //最后看从dp[m]*dp[n]的情况下转移过来是否更优
}
System.out.println(dp[n]);
}
public static void findMult(int[] dp, int m) {
List list = getYinsu(m); //获取m的因数
for (int k : list) {
if(dp[k]!=-1&&dp[m/k]!=-1) //两个数都要不为-1时才能修改
dp[m] = Math.max(dp[m], dp[k]*dp[m/k]);//判断更新较大值
}
}
public static List getYinsu(int num) {//找因数的函数
List list = new ArrayList<>();
//直接让因数从4开始，因为从dp[4]才开始有值
for (int i = 4; i*i <= num; i++) {
if (num%i==0)//能整除就加入
list.add(i);
}
return list;
}
}
注意：蓝桥杯这道题测评方面有点问题，我用最简单的输入直接给我报运行错误而不是答案错误，如图：
用自己代码测试测评数据都能得到正解
