题解 P1586 【四方定理】

pigstd · 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;
}