QwQ

OvO

题解 P1586 【四方定理】

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

2019-04-03 13:27:00 in 题解