作业帮平方数pascal问题,求大神
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/05/21 04:14:49
平方数pascal问题,求大神
【问题描述】
珍珍学习乘法时,发现4=2*2,9=3*3,…,而2不可能分解为二个相同整数的乘积,但可以分解为1*1+1*1.她想知道对任意的正整数n,把它分解为几个整数与自身相乘之和,有多少种方案呢?
【输入】输入文件square.in只有一行,该行只有一个正整数n.
【输出】输出文件square.out只有一行,该行只有一个正整数,表示总方案数.
【样例说明】
4有2种分解方案,它们是：4=1*1+1*1+1*1+1*1=2*2
13有6种分解方案,它们是：
13=1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1
=1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1+1*1+2*2
=1*1+1*1+1*1+1*1+1*1+2*2+2*2
=1*1+1*1+1*1+1*1+3*3
=1*1+2*2+2*2+2*2
=2*2+3*3
【数据限制】30%的数据,1≤n≤10; 80%的数据,1≤n≤300;100%的数据,1≤n≤800.
这道题显然是DP（不知道DP?它就是大名鼎鼎的动态规划!^_^）
楼上的算法思路是没错,但是太慢了,对于NOI严格的时间限制显然是不行的,所以我提出了更快的算法（对拍过了,绝对没有错误）
思路：一开始我直接用一维,发现不能很好处理重复,所以我采用升维的方法
设f[i,j]为对于整数i,组成它的最后一个（也就是最大的）相同整数,那么显然对于f[i],我们可以取1~根号(i)最为他的最后一项,那么也就是说,假设取了j为他的最后一个相同整数,则可知除了这个相同整数,其他相同的整数的和就是i-j^2,同时这些相同整数的和,他的最后一个相同整数不能超过j,否则就会出现比最后一个大的情况,不符合我们之前的假设,所以对于f[i,j],它是由f[i-j*j,1],f[i-j*j,2]……f[i-j*j,j]这些组成的,那么思路就很清楚了.总的算法时间复杂度平摊得O(N^2),对于本题绰绰有余.
代码：
var
f:array[0..300,0..300] of longint;
i,j,n,k,ans:longint;
begin
readln(n);
f[0,0]:=1;
for i:=1 to n do
for j:=1 to trunc(sqrt(i)) do//n^1.5次方个状态
for k:=0 to j do//状态转移
f[i,j]:=f[i,j]+f[i-sqr(j),k];//动态规划
for i:=1 to trunc(sqrt(n)) do
ans:=ans+f[n,i];//注意这里要把所有符合的都加进来,否则会遗漏
writeln(ans);
end.
不懂再追问,好的话一定要采纳啊!
楼上的算法思路是没错,但是太慢了,对于NOI严格的时间限制显然是不行的,所以我提出了更快的算法（对拍过了,绝对没有错误）
思路：一开始我直接用一维,发现不能很好处理重复,所以我采用升维的方法
设f[i,j]为对于整数i,组成它的最后一个（也就是最大的）相同整数,那么显然对于f[i],我们可以取1~根号(i)最为他的最后一项,那么也就是说,假设取了j为他的最后一个相同整数,则可知除了这个相同整数,其他相同的整数的和就是i-j^2,同时这些相同整数的和,他的最后一个相同整数不能超过j,否则就会出现比最后一个大的情况,不符合我们之前的假设,所以对于f[i,j],它是由f[i-j*j,1],f[i-j*j,2]……f[i-j*j,j]这些组成的,那么思路就很清楚了.总的算法时间复杂度平摊得O(N^2),对于本题绰绰有余.
代码：
var
f:array[0..300,0..300] of longint;
i,j,n,k,ans:longint;
begin
readln(n);
f[0,0]:=1;
for i:=1 to n do
for j:=1 to trunc(sqrt(i)) do//n^1.5次方个状态
for k:=0 to j do//状态转移
f[i,j]:=f[i,j]+f[i-sqr(j),k];//动态规划
for i:=1 to trunc(sqrt(n)) do
ans:=ans+f[n,i];//注意这里要把所有符合的都加进来,否则会遗漏
writeln(ans);
end.
不懂再追问,好的话一定要采纳啊!