题目描述
惠特利在参加世界上最好的派对:它有着无数的蛋糕!
每个蛋糕都呈具有整数边长($cm$)的正方形形状。
派对上有无限多个边长为任意整数的蛋糕。
蛋糕都有相同的高度,所以我们只考虑它们的面积。
惠特利决定吃一个或多个蛋糕,使其总面积恰好为$ N cm^2$。
你能帮他计算一下他最少需要吃掉多少个蛋糕吗?
输入格式
第一行包含整数 $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$中,唯一可行的策略是惠特利吃三个边长为 $1$ 的蛋糕。
在样例$#2$中,惠特利可以吃一个边长为 $2$ 的蛋糕。
在样例$#3$中,最好的策略是惠特利吃一个边长为 $2$ 的蛋糕和一个边长为 $1$ 的蛋糕。
算法1
(二维动态规划) $O(n^2)$
这道题看着就像背包问题
那到底是什么背包呢
我们看到第一行:
惠特利在参加世界上最好的派对:它有着无数的蛋糕!
无数的,代表这个蛋糕可以选择无数个
那说明这就是完全背包
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 10010;
int f[N];
int main(){
int t;
scanf("%d",&t);
for(int i = 1;i <= t;i ++){
memset(f,0x3f,sizeof f); //因为是求min,所以要把f数组赋值为+∞
int n;
scanf("%d",&n);
f[0] = 0; //最少吃0个蛋糕
for(int j = 1;j <= n / j;j ++){ //循环蛋糕的边长
for(int k = j * j;k <= n;k ++){ //循环当前循环的蛋糕的体积
f[k] = min(f[k],f[k - j * j] + 1);
//状态转移:
//k为当前还需要吃的蛋糕体积
//被惠特利吃掉当前边长的蛋糕
//k也要随之减少
//减少吃下的蛋糕体积
//惠特利吃下一个蛋糕,所以最后加一
}
}
printf("Case #%d: %d\n",i,f[n]); //输出答案
}
return 0;
}