1073. Square Country
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
There live square people in a square country. Everything in this country is square also. Thus, the Square Parliament has passed a law about a land. According to the law each citizen of the country has a right to buy land. A land is sold in squares, surely. Moreover, a length of a square side must be a positive integer amount of meters. Buying a square of land with a side a one pays a2 quadrics (a local currency) and gets a square certificate of a landowner.
One citizen of the country has decided to invest all of his N quadrics into the land. He can, surely, do it, buying square pieces 1 × 1 meters. At the same time the citizen has requested to minimize an amount of pieces he buys: "It will be easier for me to pay taxes," — he has said. He has bought the land successfully.
Your task is to find out a number of certificates he has gotten.
Input
The only line contains a positive integer N ≤ 60 000 , that is a number of quadrics that the citizen has invested.
Output
The only line contains a number of certificates that he has gotten.
Sample
| input | output |
|---|---|
344 |
3 |
Problem Author: Stanislav Vasilyev
Problem Source: Ural State Univerisity Personal Contest Online February'2001 Students Session
Problem Source: Ural State Univerisity Personal Contest Online February'2001 Students Session
Difficulty: 161
题意：给出x，问要多少个完全平方数相加才能得到x。
分析：dp可以解决这个问题。
dp[i]表示i最少要多少个来组成、
dp[i] = min(d[i - j*j] + 1)
但是这题有更简单的做法。
根据定理，仍和正整数可以有四个完全平方数组成。
所以说最多四个数。
这样直接暴力即可。
当然，我是弱智，做的时候没有想到。
/**
Create By yzx - stupidboy
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef double DB;
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair inline int Getint()
{
int Ret = ;
char Ch = ' ';
bool Flag = ;
while(!(Ch >= '' && Ch <= ''))
{
if(Ch == '-') Flag ^= ;
Ch = getchar();
}
while(Ch >= '' && Ch <= '')
{
Ret = Ret * + Ch - '';
Ch = getchar();
}
return Flag ? -Ret : Ret;
} const int N = ;
int n;
int dp[N]; inline void Input()
{
cin >> n;
} inline void Solve()
{
dp[] = , dp[] = ;
for(int i = ; i <= n; i++)
{
dp[i] = INF;
for(int j = ; j <= i / j; j++)
if(dp[i] > dp[i - j * j] + )
dp[i] = dp[i - j * j] + ;
}
cout << dp[n] << endl;
} int main()
{
freopen("e.in", "r", stdin);
Input();
Solve();
return ;
}