01背包 URAL 1073 Square Country

时间:2024-01-13 22:30:14

题目传送门

 /*
题意:问n最少能是几个数的平方和
01背包:j*j的土地买不买的问题
详细解释:http://www.cnblogs.com/vongang/archive/2011/10/07/2200721.html
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std; const int MAXN = 6e4 + ;
const int INF = 0x3f3f3f3f;
int dp[MAXN]; int main(void) //URAL 1073 Square Country
{
//freopen ("I.in", "r", stdin); int n;
while (scanf ("%d", &n) == )
{
memset (dp, , sizeof (dp));
for (int i=; i<=n; ++i)
{
dp[i] = dp[i-] + ;
for (int j=; j<=sqrt (n*1.0); ++j)
{
if (i >= j * j) dp[i] = min (dp[i], dp[i-j*j] + );
else break;
}
} printf ("%d\n", dp[n]);
} return ;
}