@[shooting__star](/user/955954) 建议把cnt弄到参数里
by __zhy__ @ 2024-02-04 22:58:37
@[shooting__star](/user/955954) 回溯方式假了
建议搞个数组，如果成立就直接输出
by ICU152_QWQ_IS8 @ 2024-02-04 22:59:12
可以看第二篇题解，一个数组静态记录状态，另一个数组动态跑dfs，就是第二篇题解中的 `m1` 和 `m2` 。
@[shooting__star](/user/955954)
by littlebug @ 2024-02-04 23:05:37
AC
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
int cnt;
long long fa[100005][15],f2[15];
void dfs(int a)
{
if(a==10&&cnt==n)
{
for(int i=0;i<10;++i)
fa[ans][i]=f2[i];
ans++;
return;
}
else if(a==10)
{
return;
}
for(int i=1;i<=3;i++)
{
if(cnt+i<=n)
{
f2[a]=i;
cnt+=i;
dfs(a+1);
f2[a]=0;
cnt-=i;
}
else
{
return;
}
}
}
int main()
{
cin>>n;
dfs(0);
cout<<ans<<endl;
for(int i=0;i<ans;i++)
{
for(int j=0;j<10;j++)
{
cout<<fa[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
```
by littlebug @ 2024-02-04 23:08:55
@[shooting__star](/user/955954) 从0开始dfs
by __zhy__ @ 2024-02-04 23:09:23
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
long long fa[100000][10];
long long fa2[10];
void dfs(int a,int cnt)
{
for(int i=1;i<=3;i++)
{
if(cnt+i<n)
{
fa2[a-1]=i;
cnt+=i;
if(a==10&&cnt==n)
{
ans++;
for(int i=0;i<10;i++)
{
fa[ans][i]=fa2[i];
}
return;
}
dfs(a+1,cnt);
fa2[a-1]=0;
cnt-=i;
}
else
{
return;
}
}
}
int main()
{
cin>>n;
dfs(0,0);
cout<<ans<<endl;
for(int i=0;i<ans;i++)
{
for(int j=0;j<10;j++)
{
cout<<fa[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
```
by shooting__star @ 2024-02-04 23:11:43
带上解析了（
```
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
int cnt;
long long fa[100005][15],f2[15];
//数组最好在原来的基础上再加上5,避免一些不必要的错误
//fa静态存答案,f2动态跑dfs
void dfs(int a)
{
if(a==10&&cnt==n)
{
for(int i=0;i<10;++i)
fa[ans][i]=f2[i];
ans++;
return;
}
else if(a==10)
{
return;
}
for(int i=1;i<=3;i++)
{
if(cnt+i<=n) //要用<=
{
f2[a]=i; //是a而不是a-1
cnt+=i;
dfs(a+1);
f2[a]=0;
cnt-=i;
}
else
{
return;
}
}
}
int main()
{
cin>>n;
dfs(0); //dfs从0开始
cout<<ans<<endl;
for(int i=0;i<ans;i++)
{
for(int j=0;j<10;j++)
{
cout<<fa[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
```
by littlebug @ 2024-02-04 23:15:19
递归边界最好是放在for外面（就和你最开始的那个代码一样）
by littlebug @ 2024-02-04 23:16:32
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
long long fa[100000][10];
long long fa2[10];
int cnt;
void dfs(int a)
{
if(cnt==n&&a==10)
{
ans++;
for(int i=0;i<10;i++)
{
fa[ans][i]=fa2[i];
}
return;
}
else if(a==10)
{
return;
}
for(int i=1;i<=3;i++)
{
if(cnt+i<=n)
{
fa2[a]=i;
cnt+=i;
dfs(a+1);
fa2[a]=0;
cnt-=i;
}
else
{
return;
}
}
}
int main()
{
cin>>n;
dfs(0);
cout<<ans<<endl;
for(int i=0;i<ans;i++)
{
for(int j=0;j<10;j++)
{
cout<<fa[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
```
就差一点就过样例了
by shooting__star @ 2024-02-04 23:35:53