笔试时间：2023年9月14日 秋招

第一题

题目：巧克力

小丽明天要出去和同学春游。她准备带上总面积恰好为n 的巧克力板(简化起见将巧克力板视为平面图形，忽略它的厚度，只考虑面积）去和同学们一起分享。出于美感的考虑，小丽希望她带上的巧克力板都是边长为整教的正方形，另一方面出于便携性考虑，小丽希望这些巧克力板的周长之和尽可能小。请你帮小丽找出可 能的最小周长!换句话说，小丽需要你帮忙找出k个小正方形巧克力板，边长分别为a2,a2,...,ak，使得其面积之和，即∑[1<=i<=k]ai^2，恰好为要求的总面积为n;同时使得总周长，∑[1<=i<=k]4*ai最小。

输入描述

一行，1个整数n，表示小丽希望带上的巧克力板总面积。

1<=n<=50000

输出描述

输出一行一个整数表示可能的最小周长

样例输入

11

样例输出

20

说明

我们带上三块边长分别为3、1、1的正方形巧克力板，总面积为3^2+1^2+1^2=11，此时周长为4*(3+1+1)=20。可以证明没有周长更小的方案。

参考题解

dp数组。

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[50005];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + i);
            }
        }
        System.out.println(dp[n] << 2);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
dp = [float('inf')] * 50005
dp[0] = 0
for i in range(1, n + 1):
    for j in range(i * i, n + 1):
        dp[j] = min(dp[j], dp[j - i * i] + i)
print(dp[n] <