题目描述

惠特利在参加世界上最好的派对：它有着无数的蛋糕！

每个蛋糕都呈具有整数边长（cm）的正方形形状。

派对上有无限多个边长为任意整数的蛋糕。

蛋糕都有相同的高度，所以我们只考虑它们的面积。

惠特利决定吃一个或多个蛋糕，使其总面积恰好为N cm2。

你能帮他计算一下他最少需要吃掉多少个蛋糕吗？

样例

输入格式
第一行包含整数T，表示共有T组测试数据。

每组数据占一行，包含一个整数N，为惠特利想吃掉的蛋糕的总面积。

输出格式
每组数据输出一个结果，每个结果占一行。

结果表示为“Case #x: y”，其中x是组别编号（从1开始），y是惠特利最少需要吃掉的蛋糕数量。

数据范围
1≤T≤100,
1≤N≤10000
输入样例：
3
3
4
5
输出样例：
Case #1: 3
Case #2: 1
Case #3: 2

算法1

(完全背包) $O(物品个数 * 体积)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e4 + 10;

int n;
int f[N];

int main(){
  int T = 0;
  cin >> T;
  int t = 0;
  while(T--)
  {
    cin >> n;
    t++;
    memset(f , 0x3f , sizeof(f));
    f[0] = 0;

    for(int i = 1 ; i <= n / i ; i++)
       for(int j = i * i ; j <= n ;j++)
          f[j] = min(f[j] , f[j - i * i] + 1);

    cout << "Case #" <<t << ": "  <<f[n] <<endl;
  }


  return 0;
}