完全背包求最小值
#include <iostream>
#include <cstring>
using namespace std;
int f[10010];
int main()
{
int T;
cin >> T;
for (int i = 1; i <= T; i ++ )
{
int n;
cin >> n;
for (int j = 0; j <= n; j ++)f[j] = n;
f[0] = 0;
for (int j = 0, q = 0; q <= n; j ++ ,q = j * j )
for (int k = q; k <= n; k ++ )
f[k] = min(f[k], f[k - q] + 1);
printf("Case #%d: %d\n",i,f[n]);
}
return 0;
}