Java 解法, 执行用时: 219ms, 内存消耗: 10616K, 提交时间: 2022-09-12 14:25:19

import java.util.*;

public class Main{
public static void main(String args[]){
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int [] dp = new int[8010];
    for(int i = 3; i <= n; i++)
        for(int j = 1; j < i; j++)
            dp[i] = Math.max(dp[i], (i - 1) / j * dp[j] + dp[(i - 1) % j] + i - j - 1);
    System.out.println(dp[n]);
}
}

C++14(g++5.4) 解法, 执行用时: 116ms, 内存消耗: 516K, 提交时间: 2020-07-10 22:40:56

#include<bits/stdc++.h>
using namespace std;

const int maxn=8004;

int dp[maxn];

int main(){
    int n;
    cin>>n;
    for(int i=3;i<=n;i++){
        for(int j=1;j<i;j++){
            dp[i]=max(dp[i],(i-1)/j*dp[j]+dp[(i-1)%j]+i-1-j);
        }
    }
    cout<<dp[n]<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 154ms, 内存消耗: 440K, 提交时间: 2020-07-15 00:48:01

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int i,j,n,DP[8005]={0};
	scanf("%d",&n);
	for(i=3;i<=n;i++)
		for(j=1;j<i;j++)DP[i]=max(DP[i],(i-1)/j*DP[j]+DP[(i-1)%j]+i-j-1);
	printf("%d\n",DP[n]);
    return 0;
}