题解
先f初始化为最大值,求最小蛋糕数,且蛋糕的每个价值都是1,因为求数量
这样就很简单了
#include <iostream>
#include <cstring>
using namespace std;
const int N=10010;
int f[N];
int main()
{
int n;
cin>>n;
for(int a=1;a<=n;a++)
{
int m;
cin>>m;
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=m/i;i++)//多少种蛋糕
for(int j=i*i;j<=m;j++)
f[j]=min(f[j],f[j-i*i]+1);//价值就是蛋糕数量,所以+1
printf("Case #%d: %d\n",a,f[m]);
}
}