人活着系列之平方数

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

偶然和必然？命运与意志？生与死？理性与情感？价值与非价值？在“人活着是为什么？”的问题面前都变成无意义了。婚姻？家庭？事业？爱情？这何尝不是一种借口，去诠释活着的另外一种理由，听起来显得堂而皇之一点罢了。所以活着的同时，为什么不做一做平方数？

平方数是指可以写成某个整数的平方的数。例如1,4,9等。现在我们有20个平方数，它们分别是1^2，2^2，3^2，4^2……20^2，我们想知道对于一个整数n，它可以表示成多少种平方数的和，注意每个平方数可以使用无限次。

例如 n = 10,那么

10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1;

10 = 1 + 1 + 1 + 1 + 1 + 1 + 4;

10 = 1 + 1 + 4 + 4;

10 = 1 + 9;

因此整数10可以表示成4种平方数的和。

输入

多组输入，每组输入一行，表示正整数n（1 <= n <= 500）

输出

对于每一组，输出一行，代表整数n可以表示成平方数和的种数。

示例输入

2

10

30

示例输出

1

4

27

开始的时候，没有看懂题意，后来YF说是背包，秒懂，原来是背包啊

#include <bits/stdc++.h>

#define RR freopen("input.txt","r",stdin)

#define WW freopen("ouput.txt","w",stdout)

using namespace std;

const int INF=0x3f3f3f3f;

int main()

{

    int Arr[20];

    int Dp[1000];

    for(int i=1;i<=20;i++)

    {

        Arr[i-1]=i*i;

    }

    int n;

    while(~scanf("%d",&n))

    {

        memset(Dp,0,sizeof(Dp));

        Dp[0]=1;

        for(int i=0;i<20;i++)

        {

            for(int j=Arr[i];j<=n;j++)//完全背包

            {

                Dp[j]+=Dp[j-Arr[i]];

            }

        }

        printf("%d\n",Dp[n]);

    }

    return 0;

}

版权声明：本文为博主原创文章，未经博主允许不得转载。