TImus 1073 Square Country DP

?

?

題意：給出一個數n(1<=n<=60000),這個數可以寫成一些數的平方的和，

　　　問對于n，最少可以分成多少個數的平方的和。

　　　比如：n=344，則344=18*18+4*4+2*2，輸出3.

?

dp[i]表示i這個數最少可以分成多少個數的平方的和。

?

則遍歷一邊。

?

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=60000+3;
const int inf=0x3f3f3f3f;

int dp[maxn];

int main()
{
    dp[0]=0;
    dp[1]=1;
    dp[2]=2;
    dp[3]=3;
    dp[4]=1;
    for(int i=5;i<maxn;i++)
    {
        dp[i]=inf;

        for(int j=1;j*j<=i;j++)
        {
            dp[i]=min(dp[i],dp[i-j*j]+1);
        }
    }

    int n;

    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",dp[n]);
    }

    return 0;
}

?