自动搬运

查看原文

来自洛谷，原作者为

	pigstd Hello, the cruel world.

搬运于2025-08-24 21:26:47，当前版本为作者最后更新于2019-04-03 13:27:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

update on 2020.6.26：修改了文章中的一些错误，希望管理员重新审核后通过

这道题是一道背包题，但有些题解的解释不是非常详细，所以我写了一篇题解来帮助像我一样的蒟蒻

思路：$dp[i][j]$代表 $i$用$j$个平方数所可以组成的方案数，这样对于一个$n$，只要输出 $dp[n][1-4]$的和就行了。

那么怎么计算呢？因为每个数可以用无数次，所以使用类似完全背包的方法（如果你不知道什么是完全背包，请看这道题），因为每个数$n$都可以由$n$减去一个平方数可得，则可以推出$dp[i][j]+=dp[i-k*k][j-1]$

这样就可以写出代码了：

#include<bits/stdc++.h>
using namespace std;

const int M=32768; 
int t,n;
int dp[33000][5]={1};//注意，dp[0][0]要设为1，否则会全输出0 

int main()
{
	for (int i=1;i*i<=M;i++)//枚举所有平方数 
		for (int j=i*i;j<=M;j++)//因为j-i*i要>=0(否则会RE)，所以直接从i*i开始 
			for (int sum=1;sum<=4;sum++)//枚举使用次数 
				dp[j][sum]+=dp[j-i*i][sum-1];//计算 
	cin>>t;
	while(t--)//循环t次 
	{
		int n,ans=0;
		cin>>n;
		for (int i=1;i<=4;i++)
			ans+=dp[n][i];
		cout<<ans<<endl;
	}
	return 0;
}