akl123 @ 2023-08-12 21:34:06
在下一开始写的记忆化，然后原本其他测试点都过了结果测试点2显示Segmentation fault with invalid memory reference。在下初学不太理解段错误是什么意思于是便查了一下紫书，上面似乎是说是递归次数过多导致的栈溢出，于是我便将原先的递归改为了递推，结果依然在同一个测试点上因为相同的原因RE。请问这种问题究竟应该如何解决？烦请诸位不吝赐教。 附上递推代码：
#include<iostream>
using namespace std;
long long a[21][21][21];
long long b[10001];long long c[10001];long long d[10001];long long ans[10001];
long long w(long long x, long long y,long long z)
{
if(x<=0||y<=0||z<=0)
return 1;
else
if(x>20||y>20||z>20)
return w(20,20,20);
else
if(a[x][y][z]!=0)
return a[x][y][z];
else
if(x<y&&y<z)
{
a[x][y][z]=w(x,y,z-1)+w(x,y-1,z-1)-w(x,y-1,z);
return a[x][y][z];
}
else
{
a[x][y][z]=w(x-1,y,z)+w(x-1,y-1,z)+w(x-1,y,z-1)-w(x-1,y-1,z-1);
return a[x][y][z];
}
}
int main()
{
int p,o,i;
for(p=0;p<=20;p++)
for(o=0;o<=20;o++)
for(i=0;i<=20;i++)
{
if(p==0||o==0||i==0)
{
a[p][o][i]=1;
continue;
}
else if(p<o&&o<i) a[p][o][i]=a[p][o][i-1]+a[p][o-1][i-1]-a[p][o-1][i];
else a[p][o][i]=a[p-1][o][i]+a[p-1][o-1][i]+a[p-1][o][i-1]-a[p-1][o-1][i-1];
}
for(i=0;;i++)
{
cin>>b[i]>>c[i]>>d[i];
if(b[i]==-1&&c[i]==-1&&d[i]==-1)
break;
if(b[i]<=0||c[i]<=0||d[i]<=0) ans[i]=1;
else if(b[i]>20||c[i]>20||d[i]>20) ans[i]=a[20][20][20];
else ans[i]=a[b[i]][c[i]][d[i]];
}
for(int j=0;j<i-1;j++)
cout<<"w("<<b[j]<<", "<<c[j]<<", "<<d[j]<<") = "<<ans[j]<<endl;
cout<<"w("<<b[i-1]<<", "<<c[i-1]<<", "<<d[i-1]<<") = "<<ans[i-1];
return 0;
}by rnf5114 @ 2023-08-12 21:36:25
@akl123 很简单，数组开小了
by rnf5114 @ 2023-08-12 21:38:04
顺带附上递归代码
#include <iostream>
using namespace std;
long long d[600][600][600];
int dfs(long long a,long long b,long long c){
if(a<=0||b<=0||c<=0){
return 1;
}
else if(a>20||b>20||c>20){
return dfs(20,20,20);
}
else if(a<b&&b<c){
if(d[a][b][c-1]==0)
d[a][b][c-1]=dfs(a,b,c-1);
if(d[a][b-1][c-1]==0)
d[a][b-1][c-1]=dfs(a,b-1,c-1);
if(d[a][b-1][c]==0)
d[a][b-1][c]=dfs(a,b-1,c);
return d[a][b][c-1]+d[a][b-1][c-1]-d[a][b-1][c];
}
else{
if(d[a-1][b][c]==0)
d[a-1][b][c]=dfs(a-1,b,c);
if(d[a-1][b-1][c]==0)
d[a-1][b-1][c]=dfs(a-1,b-1,c);
if(d[a-1][b][c-1]==0)
d[a-1][b][c-1]=dfs(a-1,b,c-1);
if(d[a-1][b-1][c-1]==0)
d[a-1][b-1][c-1]=dfs(a-1,b-1,c-1);
return d[a-1][b][c]+d[a-1][b-1][c]+d[a-1][b][c-1]-d[a-1][b-1][c-1];
}
}
int main(){
long long a,b,c;
while(1){
cin>>a>>b>>c;
if(a==-1&&b==-1&&c==-1){
return 0;
}
cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<dfs(a,b,c)<<endl;
}
return 0;
}
/*
┏┓ ┏┓
┏┛┻━━━┛┻┓
┃ ┃
┃ ━ ┃
┃ ┳┛ ┗┳ ┃
┃ ┃
┃ ┻ ┃
┃ ┃
┗━┓ ┏━┛Codes are far away from bugs with the animal protecting
┃ ┃ 神兽保佑,代码无bug
┃ ┃
┃ ┗━━━┓
┃ ┣┓
┃ ┏┛
┗┓┓┏━┳┓┏┛
┃┫┫ ┃┫┫
┗┻┛ ┗┻┛
*/by akl123 @ 2023-08-12 21:41:17
@rnfmabj5114 感谢！！！